?? 1476.cpp
字號:
/* This Code is Submitted by wywcgs for Problem 1476 on 2006-07-02 at 10:24:37 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 64;
const int SN = N*N*N;
const int INF = 1 << 28;
char g[N][N];
int n;
int hash(int*);
int move(int*);
int main()
{
int p[3], i, j;
while(scanf("%d", &n) != EOF && n != 0) {
for(i = 0; i < 3; i++) { scanf("%d", &p[i]); p[i]--; }
for(i = 0; i < n; i++)
for(j = 0; j < n; j++) scanf("\n%c", &g[i][j]);
int r = move(p);
if(r == INF) printf("impossible\n");
else printf("%d\n", r);
}
return 0;
}
int hash(int* p)
{
int i, r = 0; sort(p, p+3);
for(i = 0; i < 3; i++)
r |= p[i] << (i*6);
return r;
}
int move(int *b)
{
if(b[0] == b[1] && b[1] == b[2]) return 0;
int step[SN], i, j, bs = hash(b);
memset(step, -1, sizeof(step)); step[bs] = 0;
queue<int> Q; Q.push(bs);
while(!Q.empty()) {
int s = Q.front(), t = s, p[3]; Q.pop();
for(i = 0; i < 3; i++, t >>= 6) p[i] = t&63;
for(i = 0; i < 3; i++) {
int a, b;
if(i == 0) { a = p[1]; b = p[2]; }
else { a = p[0]; b = p[3-i]; }
for(j = 0; j < n; j++)
if(g[p[i]][j] == g[a][b]) {
if(a == b && b == j) return step[s]+1;
int nt[3]; memcpy(nt, p, sizeof(nt)); nt[i] = j;
int ns = hash(nt);
if(step[ns] != -1) continue;
step[ns] = step[s]+1; Q.push(ns);
}
}
}
return INF;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -