P1379 八数码naive题，STL的胜利

八数码：我使用了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函数。然后就很显然了：

 #include <cstdio>

 #include <map>

 #include <iostream>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 map<string,int>m;

 struct Node

 {

     string ss;

     int k;

 };

 queue<Node>p;

 string aim="";

 void check(Node s)

 {

     if(s.ss==aim)

     {

         printf("%d",s.k+);

         exit();

     }

     return;

 }

 void up(Node s)

 {

     int i;

     for(i=;i<=;i++) if(s.ss[i]=='') break;

     if(i<) return;

     //printf("up:i=%d ",i);cout<<s.ss;

     swap(s.ss[i],s.ss[i-]);

     //cout<<' '<<s.ss<<endl;

     check(s);

     if(m[s.ss]) return;

     m[s.ss]=;

     s.k++;

     p.push(s);

     return;

 }

 void down(Node s)

 {

     int i;

     for(i=;i<=;i++) if(s.ss[i]=='') break;

     if(i>) return;

     swap(s.ss[i],s.ss[i+]);

     check(s);

     if(m[s.ss]) return;

     m[s.ss]=;

     s.k++;

     p.push(s);

     return;

 }

 void left(Node s)

 {

     int i;

     for(i=;i<=;i++) if(s.ss[i]=='') break;

     if(i==||i==||i==) return;

     swap(s.ss[i],s.ss[i-]);

     check(s);

     if(m[s.ss]) return;

     m[s.ss]=;

     s.k++;

     p.push(s);

     return;

 }

 void right(Node s)

 {

     int i;

     for(i=;i<=;i++) if(s.ss[i]=='') break;

     if(i==||i==||i==) return;

     swap(s.ss[i],s.ss[i+]);

     check(s);

     if(m[s.ss]) return;

     m[s.ss]=;

     s.k++;

     p.push(s);

     return;

 }

 void bfs()

 {

     while(!p.empty())

     {

         Node s=p.front();

         p.pop();///取点

         //cout<<s.ss<<endl;

         up(s);

         down(s);

         left(s);

         right(s);

     }

     return;

 }

 int main()

 {

     string c;

     cin>>c;

     if(c==aim)

     {

         printf("");

         return ;

     }

     m.insert(make_pair(c,));

     Node a;

     a.ss=c;

     a.k=;

     p.push(a);

     bfs();

     return ;

 }

AC代码如下：

巴特西

P1379 八数码naive题，STL的胜利

八数码：我使用了map判重

最新文章

热门文章