111 lines
3.0 KiB
C++
111 lines
3.0 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
#include <queue>
|
|
#include <unordered_map>
|
|
using namespace std;
|
|
typedef unsigned int UI;
|
|
typedef long long LL;
|
|
unordered_map<UI, int> dist;
|
|
inline UI mp2id(char mp[4][6]) {
|
|
UI pid = 0;
|
|
UI res = 0;
|
|
UI blank_pos = 0;
|
|
for (int i = 0; i < 4; i++)
|
|
for (int j = 0; j < 4; j++) {
|
|
res <<= 1;
|
|
if (mp[i][j] == 'B')
|
|
res |= 1;
|
|
else if (mp[i][j] == 'W')
|
|
res = res;
|
|
else
|
|
blank_pos = blank_pos * 16 + pid;
|
|
pid++;
|
|
}
|
|
return (blank_pos << 16) + res;
|
|
}
|
|
inline void id2mp(UI status, char mp[4][6], int &bp1, int &bp2) {
|
|
UI blank_pos = (status >> 16) & 255;
|
|
const static int rid[16] = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3};
|
|
const static int cid[16] = {0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3};
|
|
for (int i = 0; i < 16; i++)
|
|
if (status & (1 << (15 - i)))
|
|
mp[rid[i]][cid[i]] = 'B';
|
|
else
|
|
mp[rid[i]][cid[i]] = 'W';
|
|
mp[rid[blank_pos & 15]][cid[blank_pos & 15]] = 'O';
|
|
mp[rid[(blank_pos >> 4) & 15]][cid[(blank_pos >> 4) & 15]] = 'O';
|
|
bp1 = blank_pos & 15;
|
|
bp2 = (blank_pos >> 4) & 15;
|
|
}
|
|
inline bool ok(char mp[4][6]) {
|
|
for (int i = 0; i < 4; i++) {
|
|
char c = mp[i][0];
|
|
for (int j = 1; j < 4; j++)
|
|
if (mp[i][j] != c) goto nxt1;
|
|
return true;
|
|
nxt1:;
|
|
}
|
|
for (int j = 0; j < 4; j++) {
|
|
char c = mp[0][j];
|
|
for (int i = 1; i < 4; i++)
|
|
if (mp[i][j] != c) goto nxt2;
|
|
return true;
|
|
nxt2:;
|
|
}
|
|
if (mp[0][0] == mp[1][1] && mp[1][1] == mp[2][2] && mp[2][2] == mp[3][3])
|
|
return true;
|
|
if (mp[0][3] == mp[1][2] && mp[1][2] == mp[2][1] && mp[2][1] == mp[3][0])
|
|
return true;
|
|
return false;
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
const static int rid[16] = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3};
|
|
const static int cid[16] = {0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3};
|
|
char mp[4][6], mpv[4][6];
|
|
for (int i = 0; i < 4; i++) scanf("%s", mp[i]);
|
|
UI bg = mp2id(mp);
|
|
if (ok(mp)) {
|
|
puts("0");
|
|
return 0;
|
|
}
|
|
dist[bg | (1 << 24)] = 0;
|
|
dist[bg | (0 << 24)] = 0;
|
|
queue<UI> Q;
|
|
Q.push(bg | (1 << 24));
|
|
Q.push(bg | (0 << 24));
|
|
char lch[3] = "BW";
|
|
while (Q.size()) {
|
|
UI u = Q.front();
|
|
UI ls = u >> 24;
|
|
const int d = dist[u];
|
|
Q.pop();
|
|
int bp[2];
|
|
id2mp(u, mp, bp[0], bp[1]);
|
|
for (int p = 0; p < 2; p++) {
|
|
const int blank_pos = bp[p];
|
|
const int br = rid[blank_pos], bc = cid[blank_pos];
|
|
static const int dr[4] = {0, -1, 0, 1};
|
|
static const int dc[4] = {-1, 0, 1, 0};
|
|
for (int i = 0; i < 4; i++) {
|
|
int nr = br + dr[i], nc = bc + dc[i];
|
|
if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
|
|
if (mp[nr][nc] == 'O') continue;
|
|
if (mp[nr][nc] != lch[ls]) continue;
|
|
memcpy(mpv, mp, sizeof(mp));
|
|
swap(mpv[br][bc], mpv[nr][nc]);
|
|
UI v = mp2id(mpv)|((ls^1)<<24);
|
|
if (ok(mpv)) {
|
|
printf("%d\n", d + 1);
|
|
return 0;
|
|
}
|
|
if (dist.find(v) != dist.end()) continue;
|
|
dist[v] = d + 1;
|
|
Q.push(v);
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
} |