Explain the code below, its about solving 8 puzzle using A* algorithm #include using namespace std; typedef vector> vvi; int calc(vvi & bo, vvi & best) { int ret = 0; vector> use(9); for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) { use[bo[i][j]] = {i, j}; } } for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) { ret += abs(use[best[i][j]].first - i) + abs(use[best[i][j]].second - j); } } return ret; } void print(vvi & bo) { for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) { cout << (bo[i][j] ? to_string(bo[i][j]) : " ") << " \n"[j == 2]; } } cout << '\n'; } int dx[] = {0, 1, -1, 0}; int dy[] = {1, 0, 0, -1}; vector gen(vvi & bo) { vector ret; for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) if(not bo[i][j]) { for(int k = 0; k < 4; k ++) { int ni = i + dx[k], nj = j + dy[k]; if(ni >= 0 and nj >= 0 and ni < 3 and nj < 3) { swap(bo[ni][nj], bo[i][j]); ret.emplace_back(bo); swap(bo[ni][nj], bo[i][j]); } } } } return ret; } struct state { int c = 0, s = 0; vvi p, cur; }; struct cmp { bool operator() (state & l, state & r) { return ((l.c == r.c) ? l.s > r.s : l.c > r.c); } }; int main() { priority_queue, cmp> pq; map vis; map from; map timecost; vvi bo(3, vector(3)); vvi best = bo; for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) { cin >> bo[i][j]; best[i][j] = (1 + i * 3 + j) % 9; } } state og; og.c = calc(bo, best); og.cur = bo; pq.emplace(og); while(!pq.empty()) { auto ele = pq.top(); pq.pop(); if(not vis[ele.cur]) { vis[ele.cur] = 1; from[ele.cur] = ele.p; timecost[ele.cur] = ele.s; if(not ele.c) { break; } auto children = gen(ele.cur); state te; te.p = ele.cur; te.s = ele.s + 1; for(auto child : children) { te.c = calc(child, best); te.cur = child; pq.emplace(te); } } } if(vis[best]) { stack use; vvi te = best; while(te.size()) { use.emplace(te); te = from[te]; } while(not use.empty()) { print(use.top()); use.pop(); } }
Explain the code below, its about solving 8 puzzle using A*
#include <bits/stdc++.h>
using namespace std;
typedef
int calc(vvi & bo, vvi & best) {
int ret = 0;
vector<pair<int, int>> use(9);
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) {
use[bo[i][j]] = {i, j};
}
}
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) {
ret += abs(use[best[i][j]].first - i) + abs(use[best[i][j]].second - j);
}
}
return ret;
}
void print(vvi & bo) {
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) {
cout << (bo[i][j] ? to_string(bo[i][j]) : " ") << " \n"[j == 2];
}
}
cout << '\n';
}
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
vector<vvi> gen(vvi & bo) {
vector<vvi> ret;
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) if(not bo[i][j]) {
for(int k = 0; k < 4; k ++) {
int ni = i + dx[k], nj = j + dy[k];
if(ni >= 0 and nj >= 0 and ni < 3 and nj < 3) {
swap(bo[ni][nj], bo[i][j]);
ret.emplace_back(bo);
swap(bo[ni][nj], bo[i][j]);
}
}
}
}
return ret;
}
struct state {
int c = 0, s = 0;
vvi p, cur;
};
struct cmp {
bool operator() (state & l, state & r) {
return ((l.c == r.c) ? l.s > r.s : l.c > r.c);
}
};
int main() {
priority_queue<state, vector<state>, cmp> pq;
map<vvi, int> vis;
map<vvi, vvi> from;
map<vvi, int> timecost;
vvi bo(3, vector<int>(3));
vvi best = bo;
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) {
cin >> bo[i][j];
best[i][j] = (1 + i * 3 + j) % 9;
}
}
state og;
og.c = calc(bo, best);
og.cur = bo;
pq.emplace(og);
while(!pq.empty()) {
auto ele = pq.top(); pq.pop();
if(not vis[ele.cur]) {
vis[ele.cur] = 1;
from[ele.cur] = ele.p;
timecost[ele.cur] = ele.s;
if(not ele.c) {
break;
}
auto children = gen(ele.cur);
state te;
te.p = ele.cur;
te.s = ele.s + 1;
for(auto child : children) {
te.c = calc(child, best);
te.cur = child;
pq.emplace(te);
}
}
}
if(vis[best]) {
stack<vvi> use;
vvi te = best;
while(te.size()) {
use.emplace(te);
te = from[te];
}
while(not use.empty()) {
print(use.top());
use.pop();
}
}
Step by step
Solved in 2 steps
