P1379 八数码naive题，STL的胜利-白红宇

P1379 八数码naive题，STL的胜利

阅读量：6996 次

发布时间：2019-06-27

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

八数码：我使用了map判重

结果一遍就轻松A题了。

关于map的用法：

①创建一个map

map<char,int>m;

map<string,long long int>m1;

很浅显。。。

②插入

m.insert(make_pair(19260817,"naive"));

m['R']=3;

③判重

我们只需让出现过的key的value值为1/true

那么是否出现过就是：if(m[2])

///

掌握了map的用法之后八数码就很ok了。

基本思想是广搜。我用字符串+结构体表示状态，写了4个函数为上下左右(其实没必要)，以及一个check函数。然后就很显然了：

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 using namespace std; 8 map
            
             m; 9 10 struct Node 11 { 12 string ss; 13 int k; 14 }; 15 16 queue
             
              p; 17 string aim="123804765"; 18 19 void check(Node s) 20 { 21 if(s.ss==aim) 22 { 23 printf("%d",s.k+1); 24 exit(0); 25 } 26 return; 27 } 28 29 void up(Node s) 30 { 31 int i; 32 for(i=0;i<=8;i++) if(s.ss[i]=='0') break; 33 if(i<3) return; 34 //printf("up:i=%d ",i);cout<
              
               5) return; 49 swap(s.ss[i],s.ss[i+3]); 50 check(s); 51 if(m[s.ss]) return; 52 m[s.ss]=1; 53 s.k++; 54 p.push(s); 55 return; 56 } 57 void left(Node s) 58 { 59 int i; 60 for(i=0;i<=8;i++) if(s.ss[i]=='0') break; 61 if(i==0||i==3||i==6) return; 62 swap(s.ss[i],s.ss[i-1]); 63 check(s); 64 if(m[s.ss]) return; 65 m[s.ss]=1; 66 s.k++; 67 p.push(s); 68 return; 69 } 70 void right(Node s) 71 { 72 int i; 73 for(i=0;i<=8;i++) if(s.ss[i]=='0') break; 74 if(i==2||i==5||i==8) return; 75 swap(s.ss[i],s.ss[i+1]); 76 check(s); 77 if(m[s.ss]) return; 78 m[s.ss]=1; 79 s.k++; 80 p.push(s); 81 return; 82 } 83 void bfs() 84 { 85 while(!p.empty()) 86 { 87 Node s=p.front(); 88 p.pop();///取点 89 //cout<
               
                <
                
                 >c;102 if(c==aim)103 {104 printf("0");105 return 0;106 }107 m.insert(make_pair(c,1));108 Node a;109 a.ss=c;110 a.k=0;111 p.push(a);112 bfs();113 return 0;114 }

AC代码如下：

转载于:https://www.cnblogs.com/huyufeifei/p/8663250.html

你可能感兴趣的文章