原题大意

三个棋子,通过棋盘移到同一点,只有当标线的颜色与两个对手棋子之间的标线颜色一样时,棋子才能移动.
求出最少移动的步数.
算法分析

广搜计算最小步数.

结点本身自循环,是有边的,广搜时要排除
程序代码

#include <stdio.h>
#include <memory.h>
#include <ctype.h>
int main()
{
    char g[51][51];//无向图中边的颜色
    unsigned int step[51][51][51];//棋子到达不同位置是所走的步骤
    struct str{
        char a,b,c;
    }list[51*51*51];//广搜的链表
    int i,j;
    int n;//无向图的结点数
    int a,b,c;//三个棋子的起始位置
    int flag;//能否实现目标的标志
    while(scanf("%d",&n)&&n)
    {
        scanf("%d%d%d",&a,&b,&c);
        memset(step,255,sizeof(step));
        int h=0;//链表头结点的编号 
        int t=0;//链表尾结点的编号
        //链表的第一个结点
        list[0].a=a;
        list[0].b=b;
        list[0].c=c;
        step[a][b][c]=0;
        char arrow;
        //构造无向图中边的颜色矩阵
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                while(scanf("%c",&arrow)&&!isalpha(arrow));
                g[i][j]=arrow;
            } 
        flag=0;
        //广搜
        while(h<=t)
        {
            a=list[h].a;//取出头结点 
            b=list[h].b;
            c=list[h].c;
            //判断三个棋子是否在同一位置,如果是,计算结束
            if((a==b)&&(a==c)){flag=1;break;}
            //头结点的步数值
            unsigned int current=step[a][b][c];
            current++;//移动一步
            char abcColor=g[b][c];//结点bc的颜色
            //结点a与其他各项相临边的颜色
            char *color=g[a];
            color++;
            //搜所每个相邻边
            for(i=1;i<=n;i++,color++)
            //如果不是结点a自身,该边与bc之间边颜色相同
            //而且存储的步数比当前所需步数要大
            if(i!=a&&*color==abcColor&&step[i][b][c]>current)
            {
                step[i][b][c]=current;
                t++;
                list[t].a=i;
                list[t].b=b;
                list[t].c=c;
             } 
             abcColor=g[a][c];
             color=g[b],color++;
             for(int i=1;i<=n;i++,color++)
                 if(i!=b&&*color==abcColor&&step[a][i][c]>current)
                 {
                     step[a][i][c]=current;
                     t++;
                     list[t].a=a;
                     list[t].b=i;
                     list[t].c=c;    
                }
            abcColor=g[a][b];
             color=g[c],color++;
             for(int i=1;i<=n;i++,color++)
                 if(i!=c&&*color==abcColor&&step[a][b][i]>current)
                 {
                     step[a][b][i]=current;
                     t++;
                     list[t].a=a;
                     list[t].b=b;
                     list[t].c=i;    
                }
            h++;//头结点后移 
        } 
        if(flag)printf("%u\n",step[a][b][c]);
        else printf("impossible\n");
    }

    return 0;
}