这个题其实不难。可是我用了半个下午的时间研究如何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;
}

评论