lightoj1039

CODE

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int vis[26*26*26],ncase;
int dis[26*26*26];
int dir[6][3]={0,0,1,
               0,1,0,
               1,0,0,
               -1,0,0,
               0,-1,0,
               0,0,-1};
int tran(int a,int b,int c)
{
        return a*26*26+b*26+c;
}

int main()
{
        int t;
        cin >>t;
        while(t--)
        {
                memset(vis,0,sizeof(vis));
                memset(dis,0,sizeof(dis));
                int n;
                string s,ss;
                int f=0;
                cin >> s;
                int start=(s[0]-'a')*26*26+(s[1]-'a')*26+(s[2]-'a');
                cin >> ss;
                int end=(ss[0]-'a')*26*26+(ss[1]-'a')*26+(ss[2]-'a');
                cin>>n;
                for(int i=0;i<n;i++)
                {
                        string s1,s2,s3;
                        cin >> s1>> s2>> s3;
                        for(int j=0;j<s1.size();j++)
                                for(int k=0;k<s2.size();k++)
                                        for(int l=0;l<s3.size();l++)
                                        {
                                                int tp=tran(s1[j]-'a',s2[k]-'a',s3[l]-'a');
                                                vis[tp]=1;
                                                if(tp==start||tp==end)f=1;
                                        }
                }
                cout << "Case "<<++ncase<<": ";
                if(f)
                {
                        cout << -1<<endl;
                }
                else
                {
                        queue<int> q;
                        q.push(start);
                        vis[start]=1;
                        int ans=-1;
                        while(q.size())
                        {
                                int cur=q.front();
                                if(cur==end)
                                {
                                        ans=dis[cur];
                                        break;
                                }
                                q.pop();
                                int tp=cur;
                                int z=tp%26;
                                tp/=26;
                                int y=tp%26;
                                tp/=26;
                                int x=tp%26;
                                //printf("%c %c %c\n",x+'a',y+'a',z+'a');
                                for(int i=0;i<6;i++)
                                {
                                        int cx=(x+dir[i][0]+26)%26;
                                        int cy=(y+dir[i][1]+26)%26;
                                        int cz=(z+dir[i][2]+26)%26;
                                        int tp=tran(cx,cy,cz);
                                        if(!vis[tp])
                                        {
                                                vis[tp]=1;
                                                q.push(tp);
                                                dis[tp]=dis[cur]+1;
                                        }
                                }
                        }
                        cout << ans <<endl;
                }
        }
        return 0;
}