题目

Description

"Hike on a Graph" is a game that is played on a board on which an undirected graph is drawn. The graph is complete and has all loops, i.e. for any two locations there is exactly one arrow between them. The arrows are coloured. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players may do a move. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same colour as the arrow between the two opponents' pieces.

In the sixties ("make love not war") a one-person variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.

Input

The input file contains several test cases. Each test case starts with the number $n$ . Input is terminated by $n=0$ . Otherwise, $1 \leq n \leq 50$ . Then follow three integers $p_1$ , $p_2$ , $p_3$ with $1 \leq pi\leq n$ denoting the starting locations of the game pieces. The colours of the arrows are given next as a $m×m$ matrix of whitespace-separated lower-case letters. The element mij denotes the colour of the arrow between the locations $i$ and $j$ . Since the graph is undirected, you can assume the matrix to be symmetrical.

Output

For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word "impossible" if that is not possible for the given board and starting locations.

Sample Input

3 1 2 3
r b r
b b b
r b r
2 1 2 2
y g
g y
0

Sample Output

2
impossible

Source

University of Ulm Local Contest 2000

题意

给你 $n$ 个点 $(1 \leq n \leq 50)$ 构成的完全无向图（任意两点之间都存在边包括自己到自己的边 ），三个棋子的起始位置，再给出每个点到另一个点的或者到自己的边的颜色，有 $r,g,b$ 三种颜色，分别代表 $red,green,blue$，不是重点。一个棋子从一个点走到另一个点的要求是：从该点走到另一个点的这条边的颜色只能和另外两个棋子组成的边颜色相同 ，问你三个棋子走到同一个点最少需要多少步。

分析

按照要求进行 $bfs$ .

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int MAXN=60;
int n,p1,p2,p3;
struct node
{
    int x,y,z;
    node(int _x,int _y,int _z)
    {
        x=_x;
        y=_y;
        z=_z;
    }                    //构造函数
};
char G[MAXN][MAXN];
int vis[MAXN][MAXN][MAXN];  //表示三个棋子所在位置步数
int bfs()
{
    clr(vis,0);  //未访问过的一种状态置为0
    queue <node> q;
    q.push(node(p1,p2,p3));  //初始p1,p2,p3的步数为1
    vis[p1][p2][p3]=1;  //最后答案要减一
    while(!q.empty())
    {
        node temp=q.front();
        int x=temp.x;
        int y=temp.y;
        int z=temp.z;
        q.pop();
        if(x==y&&y==z)
        {
            return vis[x][y][z];
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i][y][z]==0&&G[x][i]==G[y][z]) //按题意
            {
                vis[i][y][z]=vis[x][y][z]+1;
                q.push(node(i,y,z));
            }
            if(vis[x][i][z]==0&&G[y][i]==G[x][z])
            {
                vis[x][i][z]=vis[x][y][z]+1;
                q.push(node(x,i,z));
            }
            if(vis[x][y][i]==0&&G[z][i]==G[x][y])
            {
                vis[x][y][i]=vis[x][y][z]+1;
                q.push(node(x,y,i));
            }
        }
    }
    return -1;
}
int main()
{
    while(cin>>n,n)
    {
        cin>>p1>>p2>>p3;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>G[i][j];
            }
        }
        int ans=bfs();
        if(ans==-1)
            cout<<"impossible"<<endl;
        else
            cout<<ans-1<<endl;  //答案减一
    }
    return 0;
}