2025283 2006-08-16 19:12:19 Accepted 1103 C++ 00:00.07 1544K St.Crux 这个题其实不难。可是我用了半个下午的时间研究如何dp......这件事告诉我一个深刻的道理......下次用一个小时研究就可以了。 好吧，这个题还是有写头滴，幸好queue让我简便了不少。还有一开始看错题意，每一枚棋子是不能同时移动的。 #include <iostream>#include <fstream>#include <queue>#include <cstring>using namespace std; class pt{public: int i, k, j, c;}; queue<pt> pq, tq, ttq;int n, p1, p2, p3, b[50][50][50], ans;char a[50][50]; void init(){ p1 --, p2 --, p3 --; memset(b, 0, sizeof(b)); ans = -1; pq = tq; b[p1][p2][p3] = 1; pt tpt; tpt.i = p1, tpt.k = p2, tpt.j = p3, tpt.c = 0; pq.push(tpt);} void bfs(){ while(!pq.empty()) {  //pb();  pt tpt, ttpt;  int i, k, j;  tpt = pq.front();  if(tpt.i == tpt.k && tpt.k == tpt.j)  {   ans = tpt.c;   break;  }  for(i = 0; i < n; i ++)  {   if(a[tpt.j][tpt.k] == a[tpt.i][i])   {    k = tpt.k, j = tpt.j;    if(!b[i][k][j])    {     b[i][k][j] = 1;     ttpt.i = i, ttpt.j = j, ttpt.k = k, ttpt.c = tpt.c + 1;     pq.push(ttpt);    }   }  }  for(k = 0; k < n; k ++)  {   if(a[tpt.j][tpt.i] == a[tpt.k][k])   {    i = tpt.i, j = tpt.j;    if(!b[i][k][j])    {     b[i][k][j] = 1;     ttpt.i = i, ttpt.j = j, ttpt.k = k, ttpt.c = tpt.c + 1;     pq.push(ttpt);    }   }  }  for(j = 0; j < n; j ++)  {   if(a[tpt.i][tpt.k] == a[tpt.j][j])   {    k = tpt.k, i = tpt.i;    if(!b[i][k][j])    {     b[i][k][j] = 1;     ttpt.i = i, ttpt.j = j, ttpt.k = k, ttpt.c = tpt.c + 1;     pq.push(ttpt);    }   }  }  pq.pop(); }}    int main(){ //ifstream cin("in.txt"); while(cin >> n && n) {  cin >> p1 >> p2 >> p3;  int i, k;  for(i = 0; i < n; i ++)  {   for(k = 0; k < n; k ++)   {    cin >> a[i][k];   }  }  init();  bfs();  if(ans != -1)   printf("%d\n", ans);  else   printf("impossible\n"); } return 0;}  

评论