POJ 3221 Diamond Puzzle.-白红宇

POJ 3221 Diamond Puzzle.

阅读量：4951 次

发布时间：2019-06-11

本文共 1237 字，大约阅读时间需要 4 分钟。

~~~~

题目链接：

id=3221

显然是BFS找最优解。但是终止条件不好写。看到有一仅仅队交上去一直TLE。

比赛完了看题解原来是以目标状态为起点，BFS给每一个状态打表。用一个map映射存起来。

~~~~

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;char str[10];char s[10]="0123456";map
            
              v; //状态映射map
             
              ans; //答案映射struct node{ int t; char s[10];};//分别在0~6位置能够到达的目标位置，以-1结束。

int dir[7][4]={ {2,4,6,-1},{2,6,-1},{1,0,3,-1},{2,4,-1}, {3,0,5,-1},{4,6,-1},{1,0,5,-1} }; int Find(char* s) { for(int i=0;i<7;i++) if(s[i]=='0') return i; } int bfs() { queue<node> q; node cur,next; strcpy(cur.s,s);cur.t=0; q.push(cur); v[cur.s]=1; ans[cur.s]=0; while(!q.empty()) { cur=q.front(); q.pop(); int pos=Find(cur.s); //'0'的位置。

for(int i=0;dir[pos][i]!=-1;i++) { char temp[10]; strcpy(temp,cur.s); //交换‘0’和和对应能去的位置 swap(temp[pos],temp[dir[pos][i]]); if(!v[temp]) { v[temp]=1; strcpy(next.s,temp); next.t=cur.t+1; ans[next.s]=next.t; q.push(next); } } } } int main() { v.clear(); ans.clear(); bfs(); int T; scanf("%d",&T); while(T--) { scanf("%s",str); if(strcmp(str,s)==0) puts("0"); else printf("%d\n",ans[str]==0?-1:ans[str]); } return 0; }

转载于:https://www.cnblogs.com/jzssuanfa/p/7190846.html

你可能感兴趣的文章