Untitled
unknown
c_cpp
a year ago
3.8 kB
5
Indexable
#include <iostream> #include <queue> #include <cmath> using namespace std; #define MAX_MOVE 80 const int goalRow[] = {-1, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3}; const int goalCol[] = {-1, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2}; class State { public: int puzzle[4][4]; int heuristic; int currentMove; int prevMove; int ex, ey; State(int puzzle[4][4]) { for (int i=0; i<4; i++) for (int j=0; j<4; j++) this->puzzle[i][j] = puzzle[i][j]; this->ex = -1; this->ey = -1; this->currentMove = 0; this->prevMove = -1; setHeuristic(); } State(const State& s) { for (int i=0; i<4; i++) for (int j=0; j<4; j++) puzzle[i][j] = s.puzzle[i][j]; currentMove = s.currentMove; prevMove = s.prevMove; ex = s.ex; ey = s.ey; heuristic = s.heuristic; } void setHeuristic() { int h = 0; for (int i=0; i<4; i++) { for (int j=0; j<4; j++) { if (puzzle[i][j]) { int goalX = goalRow[puzzle[i][j]]; int goalY = goalCol[puzzle[i][j]]; h += abs(goalX - i) + abs(goalY - j); if (i == goalX) { for (int k=j; k<4; k++) { if (puzzle[i][k] > 0 && goalRow[puzzle[i][k]] == i && puzzle[i][j] > puzzle[i][k]) h += 2; } } if (j == goalY) { for (int k=i; k<4; k++) { if (puzzle[k][j] > 0 && goalCol[puzzle[k][j]] == j && puzzle[i][j] > puzzle[k][j]) h += 2; } } } } } this->heuristic = h; } void update(int i, int newx, int newy) { prevMove = i; swap(puzzle[newx][newy], puzzle[ex][ey]); ex = newx; ey = newy; currentMove++; setHeuristic(); } bool operator<(const State& rhs) const { return currentMove + heuristic > rhs.currentMove + rhs.heuristic; } }; int main() { int puzzle[4][4]; for (int i=0; i<4; i++) for (int j=0; j<4; j++) cin >> puzzle[i][j]; State s(puzzle); for (int i=0; i<4; i++) { for (int j=0; j<4; j++) { if (!puzzle[i][j]) { s.ex = i; s.ey = j; } } } priority_queue<State> pq; pq.push(s); const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; while (!pq.empty()) { State curState = pq.top(); if (curState.heuristic == 0) { cout << curState.currentMove << endl; break; } pq.pop(); if (curState.heuristic + curState.currentMove > MAX_MOVE) continue; for (int i=0; i<4; i++) { int newx = curState.ex + dx[i]; int newy = curState.ey + dy[i]; if (newx < 0 || newy < 0 || newx > 3 || newy > 3) continue; if (i == (curState.prevMove ^ 1)) continue; State nextState = curState; nextState.update(i, newx, newy); pq.push(nextState); } } if (pq.empty()) cout << -1 << endl; return 0; }
Editor is loading...
Leave a Comment