题目传送门

解题思路:

一道bfs,本题最难的一点就是如何储存已经被访问过的状态,如果直接开一个bool数组,空间肯定会炸,所以我们要用另一个数据结构存,STL大法好,用map来存,直接AC.

AC代码:

 #include<cstdio>

 #include<iostream>

 #include<map>

 #include<queue> 

 using namespace std;

 int a[][],n;

 int ans = ;

 const int dx[]={-,,,},dy[]={,-,,};

 map<int,int> m;

 inline void bfs() {

     queue<long long> q;

     q.push(n);

     m[n] = ;

     while(!q.empty()) {

         int u = q.front();

         q.pop();

         int x = ,y= ,n = u;

         if(u == ans) break;

         for(int i = ;i >= ; i--)

             for(int j = ;j >= ; j--) {

                 a[i][j] = n % ;

                 n /= ;

                 if(!a[i][j]) x = i,y = j;

             }

         for(int i = ;i < ; i++) {

             int nx = x + dx[i],ny = y + dy[i],ns = ;

             if(nx <  || ny <  || nx >  || ny > ) continue;

             swap(a[nx][ny],a[x][y]);

             for(int i = ;i <= ; i++)

                 for(int j = ;j <= ; j++)

                     ns = ns *  + a[i][j];

             if(!m.count(ns)) {

                 m[ns] = m[u] + ;

                 q.push(ns);

             }

             swap(a[nx][ny],a[x][y]);

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     bfs();

     printf("%d",m[]);

     return ;

 }

普通bfs

emmm,虽然普通bfs能A,但还是感觉太慢,所以试了一下双向bfs.

 #include<cstdio>

 #include<iostream>

 #include<queue>

 #include<map>

 using namespace std;

 int a[][],n,n1 = ;

 int x,y;

 int wayx[] = {,-,,},wayy[] = {,,,-};

 map<int,int> p,sum;

 inline void juzhen(int o) {

     for(int i = ;i >= ; i--)

         for(int j = ;j >= ; j--) {

             a[i][j] = o % ;

             o /= ;

             if(a[i][j] == ) x = i,y = j;

         }

 }

 inline void double_bfs() {

     if(n1 == ) return ;

     queue<int> step[];

     step[].push(n);

     step[].push(n1);

     sum[n] = ;

     sum[n1] = ;

     p[n] = ;p[n1] = ;

     int deep = ,s;

     while(!step[].empty() || !step[].empty()) {

         int i = ;

         while(i < ) {

             if(sum[step[i].front()] != deep) {

                 i++;

                 continue;

             }

             s = step[i].front();

             step[i].pop();

             juzhen(s);

             for(int w = ;w < ; w++) {

                 int xx = x + wayx[w];

                 int yy = y + wayy[w];

                 if(xx <  || xx >  || yy <  || yy > ) continue;

                 swap(a[x][y],a[xx][yy]);

                 int pp = ;

                 for(int j = ;j <= ; j++)

                     for(int u = ;u <= ; u++)

                         pp = pp *  + a[j][u];

                 if(p.count(pp)) {

                     if(p[pp] ==  - i) {

                         if(p[pp] == )

                             printf("%d",(deep + ) * );

                         else

                             printf("%d",deep *  + );

                         return ;

                     }

                 }

                 else {

                     step[i].push(pp);

                     sum[pp] = sum[s] + ;

                     p[pp] = i;

                 }

                 swap(a[x][y],a[xx][yy]);

             }

         }

         deep++;

     }

 }

 inline void tepan() {

     if(n == n1) printf("");

     if(n == n1) n = n1 = ;

 }

 int main()

 {

     scanf("%d",&n);

     tepan();

     double_bfs();

     return ;

 }

双向bfs

双向bfs确实快很多很多,普通bfs耗时7.38s,而双向bfs只耗时291ms,快了25倍!!!!!!

巴特西

洛谷 P1379 八数码难题(map && 双向bfs)

题目传送门

解题思路:

AC代码:

最新文章

热门文章