Алгоритм A*
Перейти к навигации
Перейти к поиску
const int SIDE = 4;
const int SIZE = SIDE * SIDE;
struct Board {
vector<int> a;
int zy, zx, manhattanHeuristic, unsolvable;
void recalculate() {
manhattanHeuristic = 0;
int inv = 0;
for (int y = 0; y < SIDE; y++) {
for (int x = 0; x < SIDE; x++) {
if (a[y * SIDE + x]) {
for (int d = 0; d < y * SIDE + x; d++)
inv += a[d] && a[d] > a[y * SIDE + x];
} else {
zy = y;
zx = x;
}
int tile = (a[y * SIDE + x] + SIZE - 1) % SIZE;
int ty = tile / SIDE, tx = tile % SIDE;
manhattanHeuristic += abs(y - ty) + abs(x - tx);
}
}
unsolvable = (inv + zy) % 2 == 0;
}
bool operator < (const Board &that) const {
if (manhattanHeuristic != that.manhattanHeuristic)
return manhattanHeuristic < that.manhattanHeuristic;
return a < that.a;
}
bool canMove(int dy, int dx) {
int ty = zy + dy, tx = zx + dx;
return 0 <= ty && ty < SIDE && 0 <= tx && tx < SIDE;
}
Board move(int dy, int dx) {
Board res = *this;
int ty = zy + dy, tx = zx + dx;
swap(res.a[zy * SIDE + zx], res.a[ty * SIDE + tx]);
res.recalculate();
return res;
}
};
istream &operator >> (istream &in, Board &board) {
board.a.resize(SIZE);
for (int i = 0; i < SIZE; i++)
in >> board.a[i];
board.recalculate();
return in;
}
string aStar(Board &board) {
if (board.unsolvable)
return "NO SOLUTION";
set<pair<int, Board>> q;
map<Board, int> dist, pred;
q.insert({ board.manhattanHeuristic, board });
dist[board] = board.manhattanHeuristic;
pred[board] = -1;
static vector<int> dy = { -1, 0, 1, 0 };
static vector<int> dx = { 0, 1, 0, -1 };
static string dc = "URDL";
while (!q.empty()) {
auto [vDist, v] = *q.begin();
q.erase(q.begin());
if (!v.manhattanHeuristic) {
board = v;
break;
}
for (int d = 0; d < 4; d++) {
if (!v.canMove(dy[d], dx[d]))
continue;
Board to = v.move(dy[d], dx[d]);
if (auto it = dist.find(to); it == dist.end() || it->second > vDist + to.manhattanHeuristic) {
q.erase({ dist[to], to });
dist[to] = vDist + to.manhattanHeuristic;
pred[to] = d;
q.insert({ dist[to], to });
}
}
}
string path;
while (1) {
int d = pred[board];
if (d == -1)
break;
path.push_back(dc[d]);
board = board.move(dy[(d + 2) % 4], dx[(d + 2) % 4]);
}
reverse(path.begin(), path.end());
return path;
}
void solve() {
Board board;
cin >> board;
cout << aStar(board) << "\n";
}