uva253

maksyuki 发表于 oj 分类，标签: 基础算法-枚举

09 12月 2017

We have a machine for painting cubes. It is supplied with three different colors: blue, red and green. Each face of the cube gets one of these colors. The cube’s faces are numbered as in Figure 1.

Since a cube has 6 faces, our machine can paint a face-numbered cube in 3 6 = 729 different ways. When ignoring the face-numbers, the number of different paintings is much less, because a cube can be rotated. See example below.

We denote a painted cube by a string of 6 characters, where each character is a ‘b’, ‘r’, or ‘g’. The i-th character (1 ≤ i ≤ 6) from the left gives the color of face i. For example, Figure 2 is a picture of “rbgggr” and Figure 3 corresponds to “rggbgr”. Notice that both cubes are painted in the same way: by rotating it around the vertical axis by 90°, the one changes into the other.

Input

The input of your program is a textfile that ends with the standard end-of-file marker. Each line is a string of 12 characters. The first 6 characters of this string are the representation of a painted cube, the remaining 6 characters give you the representation of another cube. Your program determines whether these two cubes are painted in the same way, that is, whether by any combination of rotations one can be turned into the other. (Reflections are not allowed.)

Output

The output is a file of boolean. For each line of input, output contains ‘TRUE’ if the second half can be obtained from the first half by rotation as describes above, ‘FALSE’ otherwise.

Sample Input

rbgggrrggbgr
rrrbbbrrbbbr
rbgrbgrrrrrg

Sample Output

TRUE

FALSE

题目类型：暴力枚举

算法分析：首先枚举2个对面(顶面和底面)，然后对于每个确定的两个对面，枚举(旋转)4个面，判断的条件是所有的面都相等，一个小技巧是程序中使用的index数组，可以简化生成枚举对象的过程，下面第一个代码是更好的实现

/**************************************************
filename       :n.cpp
author         :maksyuki
created time   :2017/12/8 23:16:14
last modified  :2017/12/9 8:40:30
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

const int dx[] = {1, 2, 3};
const int dy[] = {6, 5, 4};
const int dv[3][4] = {{2, 4, 5, 3}, {1, 3, 6, 4}, {1, 2, 6, 5}};

char si[66], s[6][66];
char st[6][66], sbbt[66];

void cutchar(int pv, int p) {
    int len = 1;
    for(int i = 0; i < 4; i++)
        st[p][len++] = s[p][dv[pv][i]];
}

bool rotate() {
    st[1][5] = st[2][5] = 0;
    strcpy(sbbt, st[2] + 1);
    strcat(sbbt, st[2] + 1);
    if(strstr(sbbt, st[1] + 1) != NULL) return true;
    return false;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf("%s",  si + 1) != EOF) {
        for(int i = 1; i <= 6; i++) s[1][i] = si[i];
        for(int i = 7, j = 1; i <= 12; i++, j++) s[2][j] = si[i];
        
        bool is_right = false;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++) {
                cutchar(i, 1), cutchar(j, 2);
                if(rotate() && ((s[1][dx[i]] == s[2][dx[j]] && s[1][dy[i]] == s[2][dy[j]])
                             || (s[1][dx[i]] == s[2][dy[j]] && s[1][dy[i]] == s[2][dx[j]]))) {
                    is_right = true;
                    break;
                }
            }

        if(is_right) puts("TRUE");
        else puts("FALSE");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

/**************************************************

filename :n.cpp

author :maksyuki

created time :2017/12/8 23:16:14

last modified :2017/12/9 8:40:30

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

const int dx[] = {1, 2, 3};

const int dy[] = {6, 5, 4};

const int dv[3][4] = {{2, 4, 5, 3}, {1, 3, 6, 4}, {1, 2, 6, 5}};

char si[66], s[6][66];

char st[6][66], sbbt[66];

void cutchar(int pv, int p) {

int len = 1;

for(int i = 0; i < 4; i++)

st[p][len++] = s[p][dv[pv][i]];

}

bool rotate() {

st[1][5] = st[2][5] = 0;

strcpy(sbbt, st[2] + 1);

strcat(sbbt, st[2] + 1);

if(strstr(sbbt, st[1] + 1) != NULL) return true;

return false;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(scanf("%s", si + 1) != EOF) {

for(int i = 1; i <= 6; i++) s[1][i] = si[i];

for(int i = 7, j = 1; i <= 12; i++, j++) s[2][j] = si[i];

bool is_right = false;

for(int i = 0; i < 3; i++)

for(int j = 0; j < 3; j++) {

cutchar(i, 1), cutchar(j, 2);

if(rotate() && ((s[1][dx[i]] == s[2][dx[j]] && s[1][dy[i]] == s[2][dy[j]])

|| (s[1][dx[i]] == s[2][dy[j]] && s[1][dy[i]] == s[2][dx[j]]))) {

is_right = true;

break;

}

if(is_right) puts("TRUE");

else puts("FALSE");

}

return 0;

}

#include <iostream>
#include <fstream>
using namespace std;

const int index[8][8] = {{0, 1, 2, 3, 4, 5}, {1, 5, 2, 3, 0, 4}, {2, 1, 5, 0, 4, 3}
, {3, 5, 1, 4, 0, 2}, {4, 5, 3, 2, 0, 1}, {5, 1, 3, 2, 4, 0}};


char val_a[8], val_b[8], temp[8];

bool TestRotation ()
{
	int i, j;
	for (i = 0; i < 6; i++)
	{
		for (j = 0; j < 6; j++)
			temp[j] = val_b[index[i][j]];

		for (j= 0; j < 4; j++)
		{
			char ch = temp[1];
			temp[1] = temp[2];
			temp[2] = temp[4];
			temp[4] = temp[3];
			temp[3] = ch;

			int k;
			for (k = 0; k < 6; k++)
				if (temp[k] != val_a[k])
					break;

			if (k == 6)
				return true;
		}
	}

return false;
}


int main()
{
//	ifstream cin ("aaa.txt");

	char input[18];

	while (cin >> input)
	{
		int i;
		for (i = 0; i < 6; i++)
			val_a[i] = input[i];

		for (i = 0; i < 6; i++)
			val_b[i] = input[i+6];

		if (TestRotation ())
			cout << "TRUE" << endl;

		else
			cout << "FALSE" << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

const int index[8][8] = {{0, 1, 2, 3, 4, 5}, {1, 5, 2, 3, 0, 4}, {2, 1, 5, 0, 4, 3}

, {3, 5, 1, 4, 0, 2}, {4, 5, 3, 2, 0, 1}, {5, 1, 3, 2, 4, 0}};

char val_a[8], val_b[8], temp[8];

bool TestRotation ()

{

int i, j;

for (i = 0; i < 6; i++)

{

for (j = 0; j < 6; j++)

temp[j] = val_b[index[i][j]];

for (j= 0; j < 4; j++)

{

char ch = temp[1];

temp[1] = temp[2];

temp[2] = temp[4];

temp[4] = temp[3];

temp[3] = ch;

int k;

for (k = 0; k < 6; k++)

if (temp[k] != val_a[k])

break;

if (k == 6)

return true;

}

return false;

}

int main()

{

// ifstream cin ("aaa.txt");

char input[18];

while (cin >> input)

{

int i;

for (i = 0; i < 6; i++)

val_a[i] = input[i];

for (i = 0; i < 6; i++)

val_b[i] = input[i+6];

if (TestRotation ())

cout << "TRUE" << endl;

else

cout << "FALSE" << endl;

}

return 0;

}

uva220

uva1590

超客的水墨烟雨

uva253

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31