Poj Solution 2415

http://poj.org/problem?id=2415

#include<iostream>
#include"queue"
#include"algorithm"

using namespace std;

char edge[51][51];
int sign[51][51][51],n,p1,p2,p3;
struct node
{
    int p[3];
    int steps;
};
queue<node> q;

bool init()
{
    int i,j,k;
    cin>>n>>p1>>p2>>p3;
    if(n==0)return 0;
    
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        cin>>edge[i][j];

    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    for(k=0;k<n;k++)
        sign[i][j][k]=0;
    
    while(!q.empty())
        q.pop();

    return 1;
}
inline void set(int a,int b,int c,int v)
{
    sign[a][b][c]=sign[a][c][b]=sign[b][a][c]=sign[b][c][a]=sign[c][a][b]=sign[c][b][a]=v;
}

int doit()
{
    int i,j;
    node nd,ndt;
    
    nd.p[0]=p1-1;    nd.p[1]=p2-1;    nd.p[2]=p3-1;
    nd.steps=1;

    set(nd.p[0],nd.p[1],nd.p[2],1);
    q.push(nd);
    
    while(!q.empty())
    {
        nd=q.front();q.pop();
        if(nd.p[0]==nd.p[1]&&nd.p[1]==nd.p[2])
            return sign[nd.p[0]][nd.p[1]][nd.p[2]];
        
        for(i=0;i<n;i++)
        {
            for(j=0;j<3;j++)
            if(!sign[i][nd.p[(j+1)%3]][nd.p[(j+2)%3]]&&
                edge[nd.p[j]][i]==edge[nd.p[(j+1)%3]][nd.p[(j+2)%3]])
            {
                set(i,nd.p[(j+1)%3],nd.p[(j+2)%3],nd.steps+1);
                ndt=nd;
                ndt.steps++;
                ndt.p[j]=i;
                q.push(ndt);
            }
        }
    }
    return 0;
}

int main()
{
    int ans;
    while(init())
    {
        ans=doit();
        if(!ans)cout<<"impossible"<<endl;
        else cout<<ans-1<<endl;
    }
    return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *