Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- #define MAX_TABLE 500000
- /*
- 0 = 동
- 1 = 남
- 2 = 서
- 3 = 북
- 비교
- 0 <=> 2
- 1 <=> 3
- */
- int N, M, idx[4][2];
- int puzzle[2500][4], puzzleMap[100][100];
- int arr_idx = 0;
- char input[2500][4][16];
- char otherPuzzle[16];
- int startX = 50, startY = 50;
- int minX = 99999, minY = 99999;
- struct hashNode {
- int num; // N'st puzzle
- int pairKey; // another pair puzzle
- int direction;
- hashNode* next; // next node
- } NodeValue[MAX_TABLE];
- hashNode* hashTable[MAX_TABLE];
- hashNode* hashMalloc() {
- return &NodeValue[arr_idx++];
- }
- unsigned long createHash(const char *str) {
- unsigned long hash = 5381;
- int c;
- while (c = *str++) {
- hash = (((hash << 5) + hash) + c) % MAX_TABLE;
- }
- return hash % MAX_TABLE;
- }
- void init() {
- for (int i = 0; i < 100; i++) {
- for (int j = 0; j < 100; j++) {
- puzzleMap[i][j] = -1;
- }
- }
- for (int n = 0; n < N*N; n++) {
- for (int i = 0; i < 4; i++) {
- for (int m = 0; m < M; m++) {
- cin >> input[n][i][m];
- if (input[n][i][m] == 'M') {
- otherPuzzle[m] = 'F';
- }
- else if (input[n][i][m] == 'F') {
- otherPuzzle[m] = 'M';
- }
- else {
- otherPuzzle[m] = input[n][i][m];
- }
- }
- int hashKey = createHash(input[n][i]);
- int pairKey = createHash(otherPuzzle);
- hashNode *mHashNode;
- mHashNode = hashMalloc();
- mHashNode->num = n;
- mHashNode->direction = i;
- mHashNode->next = hashTable[hashKey];
- hashTable[hashKey] = mHashNode;
- puzzle[n][i] = pairKey;
- }
- }
- for (int i = 0; i < 4; i++) {
- for (int j = 0; j < 2; j++) {
- cin >> idx[i][j];
- }
- }
- }
- void searchPuzzle(int x, int y, int num) {
- if (puzzleMap[x][y] != -1)
- return;
- if(minX >= x) {
- minX = x;
- }
- if(minY >= y) {
- minY = y;
- }
- puzzleMap[x][y] = num;
- for (int direction = 0; direction < 4; direction++) {
- int pairKey = puzzle[num][direction];
- int changeX = x;
- int changeY = y;
- for (hashNode* loopHash = hashTable[pairKey]; loopHash != nullptr; loopHash = loopHash->next) {
- if (direction == (loopHash->direction+2)%4) {
- int pairPuzzle = hashTable[pairKey]->num;
- if (direction == 0) {
- changeY++;
- }
- else if (direction == 1) {
- changeX++;
- }
- else if (direction == 2) {
- changeY--;
- }
- else if (direction == 3) {
- changeX--;
- }
- if (puzzleMap[changeX][changeY] == -1)
- searchPuzzle(changeX, changeY, pairPuzzle);
- }
- }
- }
- }
- int main() {
- cin >> N;
- cin >> M;
- init();
- searchPuzzle(startX, startY, 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement