hdu 1252 水搜索

n个点的完全图，每条边都有一个颜色，告诉你三个东西的起始位置，问最少多少步把他们移动到一起。

移动规则：若当前点要走的边和另外2个点连成的边颜色一样，则可以走。

水搜索，三维数组判重，20分钟1A，换了下char居然到第一了，2014年3月3日13:27:40

#include<cstdio>
#include<queue>
using namespace std;
int n;
int A,B,C;
char mp[51][51];
bool vis[51][51][51];
struct node
{
    char a[3];
    char dis;
}st;
void bfs()
{
    vis[st.a[0]][st.a[1]][st.a[2]]=true;
    queue<node> Q;
    Q.push(st);
    while(!Q.empty())
    {
        node t=Q.front();Q.pop();
        for(int i=0;i<3;i++)
            for(int j=1;j<=n;j++)
            {
                node f=t;
                int next1=(i+1)%3,next2=(i+2)%3;
                if(mp[f.a[i]][j]==mp[f.a[next1]][f.a[next2]])
                {
                    f.a[i]=j;
                    if(!vis[f.a[0]][f.a[1]][f.a[2]])
                    {
                        vis[f.a[0]][f.a[1]][f.a[2]]=true;
                        f.dis++;
                        Q.push(f);
                        if(f.a[0]==f.a[1]&&f.a[1]==f.a[2]) {printf("%d\n",f.dis);return;}
                    }
                }
            }
    }puts("impossible");
}
int main()
{
    st.dis=0;
    while(scanf("%d",&n)&&n)
    {
        scanf("%d%d%d",&A,&B,&C);
        st.a[0]=A;st.a[1]=B;st.a[2]=C;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%s",&mp[i][j]);
        if(st.a[0]==st.a[1]&&st.a[1]==st.a[2]) puts("0");
        else bfs();
    }
    return 0;
}

hdu 1252 水搜索,布布扣,bubuko.com

hdu 1252 水搜索

原文：http://blog.csdn.net/t1019256391/article/details/20368979