SHARE
TWEET

Untitled

a guest Oct 18th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<math.h>
  3. #include<queue>
  4. #include <unordered_set>
  5. using namespace std;
  6.  
  7. int manhattanDistance(int** board, int boardSize)
  8. {
  9.     int sum = 0;
  10.     int shouldBeI, shouldBeJ;
  11.     int cellValue;
  12.  
  13.     for(int i=0; i<boardSize; i++)
  14.     {
  15.         for(int j=0; j<boardSize; j++)
  16.         {
  17.             cellValue = board[i][j];
  18.             if(board[i][j] == 0)
  19.             {
  20.                 shouldBeI = shouldBeJ = boardSize - 1;
  21.             }
  22.             else
  23.             {
  24.                 shouldBeI = (cellValue - 1) / boardSize;
  25.                 shouldBeJ = (cellValue - 1) % boardSize;
  26.             }
  27.             sum += abs(i - shouldBeI) + abs(j - shouldBeJ);
  28.         }
  29.     }
  30.     return sum;
  31. }
  32.  
  33. void printBoard(int** board, int boardSize)
  34. {
  35.     for(int i=0; i<boardSize; i++)
  36.     {
  37.         for(int j=0; j<boardSize; j++)
  38.         {
  39.             cout<<board[i][j]<<" ";
  40.         }
  41.         cout<<endl;
  42.     }
  43. }
  44.  
  45. int** copyBoard(int** board, int boardSize)
  46. {
  47.     int** newBoard = new int*[boardSize];
  48.     for(int i=0; i<boardSize; i++)
  49.     {
  50.         newBoard[i] = new int[boardSize];
  51.         for(int j=0; j<boardSize; j++)
  52.         {
  53.             newBoard[i][j] = board[i][j];
  54.         }
  55.     }
  56.  
  57.     return newBoard;
  58. }
  59.  
  60. struct BoardStatus
  61. {
  62.     int** board;
  63.     int boardSize;
  64.     int distanceSoFar;
  65.     string trace;
  66.     int manhattanDist;
  67.     int zeroRow;
  68.     int zeroCol;
  69.  
  70.     bool canMoveLeft()
  71.     {
  72.         return zeroCol < boardSize - 1;
  73.     }
  74.  
  75.     BoardStatus* moveLeft()
  76.     {
  77.         BoardStatus* result = new BoardStatus(*this);
  78.         result->board[result->zeroRow][result->zeroCol] =
  79.             result->board[result->zeroRow][result->zeroCol + 1];
  80.         result->board[result->zeroRow][result->zeroCol + 1] = 0;
  81.         result->zeroCol += 1;
  82.         result->manhattanDist = manhattanDistance(result->board, result->boardSize);
  83.         result->distanceSoFar += 1;
  84.         result->trace = result->trace + "l";
  85.  
  86.         return result;
  87.     }
  88.  
  89.     bool canMoveRight()
  90.     {
  91.         return zeroCol > 0;
  92.     }
  93.  
  94.     BoardStatus* moveRight()
  95.     {
  96.         BoardStatus* result = new BoardStatus(*this);
  97.         result->board[result->zeroRow][result->zeroCol] =
  98.             result->board[result->zeroRow][result->zeroCol - 1];
  99.         result->board[result->zeroRow][result->zeroCol - 1] = 0;
  100.         result->zeroCol -= 1;
  101.         result->manhattanDist = manhattanDistance(result->board, result->boardSize);
  102.         result->distanceSoFar += 1;
  103.         result->trace = result->trace + "r";
  104.  
  105.         return result;
  106.     }
  107.  
  108.     bool canMoveUp()
  109.     {
  110.         return zeroRow < boardSize - 1;
  111.     }
  112.  
  113.     BoardStatus* moveUp()
  114.     {
  115.         BoardStatus* result = new BoardStatus(*this);
  116.         result->board[result->zeroRow][result->zeroCol] =
  117.             result->board[result->zeroRow + 1][result->zeroCol];
  118.         result->board[result->zeroRow + 1][result->zeroCol] = 0;
  119.         result->zeroRow += 1;
  120.         result->manhattanDist = manhattanDistance(result->board, result->boardSize);
  121.         result->distanceSoFar += 1;
  122.         result->trace = result->trace + "u";
  123.  
  124.         return result;
  125.     }
  126.  
  127.     bool canMoveDown()
  128.     {
  129.         return zeroRow > 0;
  130.     }
  131.  
  132.     BoardStatus* moveDown()
  133.     {
  134.         BoardStatus* result = new BoardStatus(*this);
  135.         result->board[result->zeroRow][result->zeroCol] =
  136.             result->board[result->zeroRow - 1][result->zeroCol];
  137.         result->board[result->zeroRow - 1][result->zeroCol] = 0;
  138.         result->zeroRow -= 1;
  139.         result->manhattanDist = manhattanDistance(result->board, result->boardSize);
  140.         result->distanceSoFar += 1;
  141.         result->trace = result->trace + "d";
  142.  
  143.         return result;
  144.     }
  145.  
  146.     BoardStatus(int** board, int boardSize, int distanceSoFar, string trace)
  147.     {
  148.         this->board = copyBoard(board, boardSize);
  149.         this->boardSize = boardSize;
  150.         this->distanceSoFar = distanceSoFar;
  151.         this->trace = trace;
  152.         this->manhattanDist = manhattanDistance(this->board, this->boardSize);
  153.  
  154.         for(int i=0; i<boardSize; i++)
  155.         {
  156.             for(int j=0; j<boardSize; j++)
  157.             {
  158.                 if(board[i][j] == 0)
  159.                 {
  160.                     this->zeroRow = i;
  161.                     this->zeroCol = j;
  162.                 }
  163.             }
  164.         }
  165.     }
  166.  
  167.     BoardStatus(const BoardStatus& other)
  168.     {
  169.         this->board = copyBoard(other.board, other.boardSize);
  170.         this->boardSize = other.boardSize;
  171.         this->distanceSoFar = other.distanceSoFar;
  172.         this->trace = other.trace;
  173.         this->manhattanDist = manhattanDistance(this->board, this->boardSize);
  174.         this->zeroCol = other.zeroCol;
  175.         this->zeroRow = other.zeroRow;
  176.     }
  177.  
  178.     BoardStatus& operator=(const BoardStatus& other)
  179.     {
  180.         if(this != &other)
  181.         {
  182.             this->board = copyBoard(other.board, other.boardSize);
  183.             this->boardSize = other.boardSize;
  184.             this->distanceSoFar = other.distanceSoFar;
  185.             this->trace = other.trace;
  186.             this->manhattanDist = manhattanDistance(this->board, this->boardSize);
  187.             this->zeroCol = other.zeroCol;
  188.             this->zeroRow = other.zeroRow;
  189.         }
  190.         return *this;
  191.     }
  192.  
  193.     ~BoardStatus()
  194.     {
  195.         for(int i=0; i<this->boardSize; i++)
  196.         {
  197.             delete[] board[i];
  198.         }
  199.         delete[] board;
  200.     }
  201.  
  202.     bool operator ==(const BoardStatus &other) const
  203.     {
  204.         if(this->boardSize != other.boardSize)
  205.         {
  206.             return false;
  207.         }
  208.         for(int i=0; i< this->boardSize; i++)
  209.         {
  210.             for(int j=0; j< this->boardSize; j++)
  211.             {
  212.                 if(this->board[i][j] != other.board[i][j])
  213.                 {
  214.                     return false;
  215.                 }
  216.             }
  217.         }
  218.  
  219.         return true;
  220.     }
  221.  
  222.     bool operator<(const BoardStatus &other) const
  223.     {
  224.         return this->distanceSoFar + this->manhattanDist > other.distanceSoFar + other.manhattanDist;
  225.     }
  226.  
  227.     void print()
  228.     {
  229.         printBoard(this->board, this->boardSize);
  230.         cout<<this->distanceSoFar<<" "<<this->manhattanDist<<" "<<this->trace<<endl;
  231.         cout<<zeroRow<<" "<<zeroCol<<endl;
  232.         cout<<"--------------------------------------"<<endl;
  233.     }
  234.  
  235.     void printResult()
  236.     {
  237.         cout<<this->distanceSoFar<<endl;
  238.         for(int i=0; i < this->trace.length(); i++)
  239.         {
  240.             if(this->trace[i] == 'u')
  241.             {
  242.                 cout<<"up"<<endl;
  243.             }
  244.             else if(this->trace[i] == 'r')
  245.             {
  246.                 cout<<"right"<<endl;
  247.             }
  248.             else if(this->trace[i] == 'd')
  249.             {
  250.                 cout<<"down"<<endl;
  251.             }
  252.             else if(this->trace[i] == 'l')
  253.             {
  254.                 cout<<"left"<<endl;
  255.             }
  256.         }
  257.     }
  258. };
  259.  
  260. struct BoardStatusHash
  261. {
  262.     std::size_t operator () ( const BoardStatus& b ) const
  263.     {
  264.         int hash = 0;
  265.         for(int i=0; i < b.boardSize; i++)
  266.         {
  267.             for(int j=0; j < b.boardSize; j++)
  268.             {
  269.                 hash += (i*b.boardSize + j) * b.board[i][j];
  270.             }
  271.         }
  272.         return hash;
  273.     }
  274. };
  275.  
  276. void astar(int** board, int boardSize)
  277. {
  278.     BoardStatus start(board, boardSize, 0, "");
  279.  
  280.     unordered_set<BoardStatus, BoardStatusHash> visited;
  281.     priority_queue<BoardStatus> pq;
  282.     pq.push(start);
  283.  
  284.     BoardStatus top = pq.top();
  285.     visited.insert(top);
  286.  
  287.     while(!pq.empty() && top.manhattanDist > 0)
  288.     {
  289.         pq.pop();
  290.         if(top.canMoveUp())
  291.         {
  292.             BoardStatus* movedUp = top.moveUp();
  293.             if(visited.count(*movedUp) == 0)
  294.             {
  295.                 pq.push(*movedUp);
  296.             }
  297.         }
  298.         if(top.canMoveRight())
  299.         {
  300.             BoardStatus* movedRight = top.moveRight();
  301.             if(visited.count(*movedRight) == 0)
  302.             {
  303.                 pq.push(*movedRight);
  304.             }
  305.         }
  306.         if(top.canMoveDown())
  307.         {
  308.             BoardStatus* movedDown = top.moveDown();
  309.             if(visited.count(*movedDown) == 0)
  310.             {
  311.                 pq.push(*movedDown);
  312.             }
  313.         }
  314.         if(top.canMoveLeft())
  315.         {
  316.             BoardStatus* movedLeft = top.moveLeft();
  317.             if(visited.count(*movedLeft) == 0)
  318.             {
  319.                 pq.push(*movedLeft);
  320.             }
  321.         }
  322.  
  323.  
  324.         top = pq.top();
  325.         visited.insert(top);
  326.     }
  327.  
  328.     top.printResult();
  329. }
  330.  
  331. int main()
  332. {
  333.     int N;
  334.     cout<<"Enter number of enumerated tiles: ";
  335.     cin>>N;
  336.     int n = sqrt(N+1);
  337.  
  338.     cout<<"Enter game board: "<<endl;
  339.     int** board = new int*[n];
  340.     for(int i=0; i<n; i++)
  341.     {
  342.         board[i] = new int[n];
  343.         for(int j=0; j<n; j++)
  344.         {
  345.             cin>>board[i][j];
  346.         }
  347.     }
  348.  
  349.     astar(board, n);
  350. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top