Advertisement
Guest User

Untitled

a guest
Feb 17th, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define MAX_TABLE 500000
  5.  
  6. /*
  7. 0 = 동
  8. 1 = 남
  9. 2 = 서
  10. 3 = 북
  11.  
  12. 비교
  13. 0 <=> 2
  14. 1 <=> 3
  15. */
  16.  
  17. int N, M, idx[4][2];
  18. int puzzle[2500][4], puzzleMap[100][100];
  19. int arr_idx = 0;
  20. char input[2500][4][16];
  21. char otherPuzzle[16];
  22. int startX = 50, startY = 50;
  23. int minX = 99999, minY = 99999;
  24.  
  25. struct hashNode {
  26.     int num; // N'st puzzle
  27.     int pairKey; // another pair puzzle
  28.     int direction;
  29.     hashNode* next; // next node
  30. } NodeValue[MAX_TABLE];
  31.  
  32. hashNode* hashTable[MAX_TABLE];
  33.  
  34. hashNode* hashMalloc() {
  35.     return &NodeValue[arr_idx++];
  36. }
  37.  
  38. unsigned long createHash(const char *str) {
  39.  
  40.     unsigned long hash = 5381;
  41.     int c;
  42.  
  43.     while (c = *str++) {
  44.         hash = (((hash << 5) + hash) + c) % MAX_TABLE;
  45.     }
  46.     return hash % MAX_TABLE;
  47. }
  48.  
  49. void init() {
  50.  
  51.     for (int i = 0; i < 100; i++) {
  52.         for (int j = 0; j < 100; j++) {
  53.             puzzleMap[i][j] = -1;
  54.         }
  55.     }
  56.  
  57.     for (int n = 0; n < N*N; n++) {
  58.         for (int i = 0; i < 4; i++) {
  59.             for (int m = 0; m < M; m++) {
  60.  
  61.                 cin >> input[n][i][m];
  62.  
  63.                 if (input[n][i][m] == 'M') {
  64.                     otherPuzzle[m] = 'F';
  65.                 }
  66.                 else if (input[n][i][m] == 'F') {
  67.                     otherPuzzle[m] = 'M';
  68.                 }
  69.                 else {
  70.                     otherPuzzle[m] = input[n][i][m];
  71.                 }
  72.             }
  73.  
  74.             int hashKey = createHash(input[n][i]);
  75.             int pairKey = createHash(otherPuzzle);
  76.  
  77.             hashNode *mHashNode;
  78.             mHashNode = hashMalloc();
  79.             mHashNode->num = n;
  80.             mHashNode->direction = i;
  81.             mHashNode->next = hashTable[hashKey];
  82.             hashTable[hashKey] = mHashNode;
  83.  
  84.             puzzle[n][i] = pairKey;
  85.         }
  86.     }
  87.  
  88.     for (int i = 0; i < 4; i++) {
  89.         for (int j = 0; j < 2; j++) {
  90.             cin >> idx[i][j];
  91.         }
  92.     }
  93. }
  94.  
  95. void searchPuzzle(int x, int y, int num) {
  96.  
  97.     if (puzzleMap[x][y] != -1)
  98.         return;
  99.  
  100.     if(minX >= x) {
  101.         minX = x;
  102.     }
  103.  
  104.     if(minY >= y) {
  105.         minY = y;
  106.     }
  107.    
  108.     puzzleMap[x][y] = num;
  109.    
  110.     for (int direction = 0; direction < 4; direction++) {
  111.  
  112.         int pairKey = puzzle[num][direction];
  113.         int changeX = x;
  114.         int changeY = y;
  115.  
  116.         for (hashNode* loopHash = hashTable[pairKey]; loopHash != nullptr; loopHash = loopHash->next) {
  117.            
  118.             if (direction == (loopHash->direction+2)%4) {
  119.                
  120.                 int pairPuzzle = hashTable[pairKey]->num;
  121.  
  122.                 if (direction == 0) {
  123.                     changeY++;
  124.                 }
  125.                 else if (direction == 1) {
  126.                     changeX++;
  127.                 }
  128.                 else if (direction == 2) {
  129.                     changeY--;
  130.                 }
  131.                 else if (direction == 3) {
  132.                     changeX--;
  133.                 }
  134.  
  135.                 if (puzzleMap[changeX][changeY] == -1)
  136.                     searchPuzzle(changeX, changeY, pairPuzzle);
  137.             }
  138.         }
  139.     }
  140. }
  141.  
  142. int main() {
  143.  
  144.     cin >> N;
  145.     cin >> M;
  146.  
  147.     init();
  148.     searchPuzzle(startX, startY, 0);
  149.  
  150.     return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement