poj 1184 广搜进阶题

起初的想法果然就是一个6000000的状态的表示。
但是后面觉得还是太过于幼稚了。
可以看看网上的解释，其实就是先转换位置，然后再改变数字的大小。
  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<queue>
  6 #include<cmath>
  7 using std::swap;
  8 using std::queue;
  9 int const INF = 10000000;
 10 int const N = 6;
 11 struct node
 12 {
 13        int num[N];
 14        int pos,step,sta;
 15 }cur,nt;
 16 int vis[N][N][N][N][N][N][N][10];
 17 node record[720];
 18 int visp[10][N]=
 19 {
 20     1,0,0,0,0,0,
 21     1,1,0,0,0,0,
 22     1,1,1,0,0,0,
 23     1,1,1,1,0,0,
 24     1,1,1,1,1,0,
 25     1,0,0,0,0,1,
 26     1,1,0,0,0,1,
 27     1,1,1,0,0,1,
 28     1,1,1,1,0,1,
 29     1,1,1,1,1,1,
 30 };
 31 char start[N+1],end1[N+1];
 32 int cnt;
 33 void system()
 34 {
 35      char tmp[5];
 36      printf("Press 0 to continue
");
 37      while(scanf("%s",tmp))
 38      {
 39            if(tmp[0]=='0')break;
 40      }
 41 }
 42 bool judge(node tmp)
 43 {
 44      return vis[tmp.num[0]][tmp.num[1]][tmp.num[2]][tmp.num[3]][tmp.num[4]][tmp.num[5]][tmp.pos][tmp.sta];
 45 }
 46 void CreateVis(node tmp)
 47 {
 48      vis[tmp.num[0]][tmp.num[1]][tmp.num[2]][tmp.num[3]][tmp.num[4]][tmp.num[5]][tmp.pos][tmp.sta]=1;
 49 }
 50 void bfs()
 51 {
 52      for(int i=0;i<N;i++)cur.num[i]=i;
 53      cur.pos=cur.sta=cur.step=0;
 54      CreateVis(cur);
 55      queue<node> q;
 56      q.push(cur);
 57      while(!q.empty())
 58      {
 59            cur=q.front();
 60            q.pop();
 61            for(int i=0;i<N;i++)
 62                record[cnt].num[i]=cur.num[i];
 63            record[cnt].step=cur.step;
 64            record[cnt].pos=cur.pos;
 65            record[cnt++].sta=cur.sta;
 66            if(cur.pos>0)
 67            {
 68               nt=cur;
 69               nt.step=cur.step+1;
 70               swap(nt.num[0],nt.num[nt.pos]);
 71               if(!judge(nt))
 72               {
 73                  q.push(nt);
 74                  CreateVis(nt);
 75               }
 76            }
 77            if(cur.pos<5)
 78            {
 79               nt=cur;
 80               nt.pos++;
 81               nt.sta++;
 82               nt.step=cur.step+1;
 83               if(!judge(nt))
 84               {
 85                  q.push(nt);
 86                  CreateVis(nt);
 87               }
 88               nt=cur;
 89               if(nt.sta<5)
 90               nt.sta+=5;
 91               nt.step=cur.step+1;
 92               swap(nt.num[5],nt.num[nt.pos]);
 93               if(!judge(nt))
 94               {
 95                  q.push(nt);
 96                  CreateVis(nt);
 97               }
 98            }
 99      }
100 }
101 int Min(int a,int b)
102 {
103     return a<b?a:b;
104 }
105 int main()
106 {
107     cnt=0;
108     memset(vis,0,sizeof(vis));
109     bfs();
110     while(~scanf("%s %s",start,end1))
111     {
112           start[6]='';
113           end1[6]='';
114           //printf("len=%d
",len);
115           for(int i=0;i<6;i++)
116           {
117               start[i]=start[i]-'0';
118               end1[i]=end1[i]-'0';
119           }
120           int step=0,flag,ans=INF;
121           for(int i=0;i<cnt;i++)
122           {
123               step=record[i].step;
124               flag=1;
125               for(int j=0;j<N;j++)
126               {
127                   if(!visp[record[i].sta][j]&&start[record[i].num[j]]!=end1[j])
128                   {
129                      flag=0;break;
130                   }
131                   else
132                     step+=abs(start[record[i].num[j]]-end1[j]);
133               }
134               if(flag)
135                  ans=Min(ans,step);
136           }
137           printf("%d
",ans);
138     }
139     return 0;
140 }
View Code