CHESSCBG - Bàn cờ thế
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int tl;
string a, b;
int num[5][5], cnt;
vector<int> pos[20];
int Q[1 << 17], d[1 << 17];
bool was[1 << 17];
void Enter() {
string s;
int i, j, d;
for(i=1; i<5; i++) {
getline(cin, s);
a = a + s;
}
for(i=1; i<5; i++) {
getline(cin, s);
b = b + s;
}
for(i=1; i<5; i++)
for(j=1; j<5; j++)
num[i][j] = ++cnt;
int x, y;
for(i=1; i<5; i++)
for(j=1; j<5; j++) {
for(d=0; d<4; d++) {
x = i + dx[d]; y = j + dy[d];
if (x<1 || y<1 || x>4 || y>4) continue;
pos[16 - num[i][j]].push_back(16 - num[x][y]);
}
}
}
void BFS() {
bitset<16> s (a);
bitset<16> t (b);
bitset<16> v;
tl = t.to_ulong();
int l = 1, r = 1, ul, vl, i, j, p;
Q[1] = s.to_ulong();
was[Q[1]] = true;
while (l <= r) {
ul = Q[l++];
bitset<16> u (ul);
for(i=0; i<16; i++)
if (u[i] == 1) {
for(j=0; j<pos[i].size(); j++) {
p = pos[i][j];
if (u[p] == 0) {
v = u;
v.flip(i); v.flip(p);
vl = v.to_ulong();
if (was[vl]) continue;
Q[++r] = vl;
was[vl] = true;
d[vl] = d[ul] + 1;
if (vl == tl) return;
}
}
}
}
}
int main()
{
Enter();
BFS();
printf("%d", d[tl]);
return 0;
}