在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入初始状态,一行九个数字,空格用0表示
输出格式:只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
- 283104765
- 4
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <map>
- #include <queue>
- #include <cstring>
- #include <string>
- using namespace std;
- const string s_end = "123804765";
- struct Node{
- string s;
- int step;
- };
- queue <Node> Q1;
- map <string, bool> mp;
- string s_start;
- int Step;
- inline void pd(string ss, int answer)
- {
- if(ss == s_end)
- {
- printf("%d",answer);
- exit(0);
- }
- }
- inline void bfs()
- {
- while(!Q1.empty())
- {
- Node topp = Q1.front();
- Q1.pop();
- string s1 = topp.s;
- Step = topp.step;
- int f = s1.find(‘0‘);
- Node nxt;
- if(f == 0)
- {
- swap(s1[0], s1[1]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; } swap(s1[0], s1[1]);
- swap(s1[0], s1[3]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 1)
- {
- swap(s1[0], s1[1]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[0], s1[1]);
- swap(s1[1], s1[2]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[1], s1[2]);
- swap(s1[1], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 2)
- {
- swap(s1[1], s1[2]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[1], s1[2]);
- swap(s1[2], s1[5]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 3)
- {
- swap(s1[0], s1[3]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[0], s1[3]);
- swap(s1[3], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[3], s1[4]);
- swap(s1[3], s1[6]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 4)
- {
- swap(s1[1], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[1], s1[4]);
- swap(s1[3], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[3], s1[4]);
- swap(s1[5], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[5], s1[4]);
- swap(s1[7], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 5)
- {
- swap(s1[5], s1[2]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[5], s1[2]);
- swap(s1[5], s1[4]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[5], s1[4]);
- swap(s1[5], s1[8]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 6)
- {
- swap(s1[6], s1[3]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[6], s1[3]);
- swap(s1[6], s1[7]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 7)
- {//4 7 6 7 8 7
- swap(s1[4], s1[7]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[4], s1[7]);
- swap(s1[6], s1[7]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[6], s1[7]);
- swap(s1[8], s1[7]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }continue;
- }
- if(f == 8)
- {//58 78
- swap(s1[5], s1[8]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1; }swap(s1[5], s1[8]);
- swap(s1[7], s1[8]);pd(s1, topp.step + 1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = 1;}continue;
- }
- }
- }
- int main()
- {
- cin >> s_start;
- Node now;
- now.s = s_start;
- now.step = 0;
- Q1.push(now);
- bfs();
- return 0;
- }
- //283104765
双向bfs竟然超时
- // 双向 bfs
- /*
- 是否已经被正向搜到了,且用了多少步 map <string, int> is_front; 注意,这个map只存储正向搜到的状态
- 正反两个队列
- 分别存储当前状态以及所用步数
- 正反交替进行
- 每当反向搜到 map[当前状态] != 0 时, answer = map[当前状态] + 反向搜到的步数
- */
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <map>
- #include <queue>
- #include <cstring>
- #include <string>
- using namespace std;
- const string s_end = "123804765";
- struct Node{
- string s;
- int step;
- };
- string s_start;
- queue <Node> Q1;
- queue <Node> Q2;
- map <string, int> mp;
- map <string, int> mp_back;
- inline void pd(string ss, int answer){if(ss == s_end){printf("%d", answer);exit(0);}}
- inline void pd_out(int a, int answer, string ss){if(a){printf("%d",answer);exit(0);}}
- void bfs_front();
- inline void bfs_back()
- {
- while(1)
- {
- Node topp = Q2.front();
- Q2.pop();
- string now = topp.s;
- int f = now.find(‘0‘);
- string s1 = now;
- Node nxt;
- if(f == 0)
- {
- swap(s1[0], s1[1]);pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[0], s1[1]);
- swap(s1[0], s1[3]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 1)
- {
- swap(s1[0], s1[1]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[0], s1[1]);
- swap(s1[1], s1[2]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[1], s1[2]);
- swap(s1[1], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 2)
- {
- swap(s1[1], s1[2]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[1], s1[2]);
- swap(s1[2], s1[5]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 3)
- {
- swap(s1[0], s1[3]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[0], s1[3]);
- swap(s1[3], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[3], s1[4]);
- swap(s1[3], s1[6]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 4)
- {
- swap(s1[1], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[1], s1[4]);
- swap(s1[3], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[3], s1[4]);
- swap(s1[5], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[5], s1[4]);
- swap(s1[7], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 5)
- {
- swap(s1[5], s1[2]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[5], s1[2]);
- swap(s1[5], s1[4]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[5], s1[4]);
- swap(s1[5], s1[8]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 6)
- {
- swap(s1[6], s1[3]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[6], s1[3]);
- swap(s1[6], s1[7]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 7)
- {//4 7 6 7 8 7
- swap(s1[4], s1[7]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[4], s1[7]);
- swap(s1[6], s1[7]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[6], s1[7]);
- swap(s1[8], s1[7]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- if(f == 8)
- {//58 78
- swap(s1[5], s1[8]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}swap(s1[5], s1[8]);
- swap(s1[7], s1[8]); pd_out(mp[s1], topp.step + mp[s1] + 1, s1);
- if(!mp_back[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q2.push(nxt);mp_back[s1] = nxt.step;}continue;
- }
- return ;
- }
- }
- inline void bfs_front()//正向 bfs
- {
- while(1)
- {
- Node topp = Q1.front();
- Q1.pop();
- string now = topp.s;
- int f = now.find(‘0‘);
- Node nxt;
- string s1 = now;
- if(f == 0)
- {
- swap(s1[0], s1[1]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[0], s1[1]);
- swap(s1[0], s1[3]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 1)
- {
- swap(s1[0], s1[1]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[0], s1[1]);
- swap(s1[1], s1[2]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[1], s1[2]);
- swap(s1[1], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 2)
- {
- swap(s1[1], s1[2]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[1], s1[2]);
- swap(s1[2], s1[5]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 3)
- {
- swap(s1[0], s1[3]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[0], s1[3]);
- swap(s1[3], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[3], s1[4]);
- swap(s1[3], s1[6]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 4)
- {
- swap(s1[1], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[1], s1[4]);
- swap(s1[3], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[3], s1[4]);
- swap(s1[5], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[5], s1[4]);
- swap(s1[7], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 5)
- {
- swap(s1[5], s1[2]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[5], s1[2]);
- swap(s1[5], s1[4]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[5], s1[4]);
- swap(s1[5], s1[8]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 6)
- {
- swap(s1[6], s1[3]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[6], s1[3]);
- swap(s1[6], s1[7]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 7)
- {//4 7 6 7 8 7
- swap(s1[4], s1[7]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[4], s1[7]);
- swap(s1[6], s1[7]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[6], s1[7]);
- swap(s1[8], s1[7]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- if(f == 8)
- {//58 78
- swap(s1[5], s1[8]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}swap(s1[5], s1[8]);
- swap(s1[7], s1[8]);pd(s1, topp.step + 1);pd_out(mp_back[s1], topp.step + mp_back[s1] + 1, s1);
- if(!mp[s1]){nxt.s = s1;nxt.step = topp.step + 1;Q1.push(nxt);mp[s1] = nxt.step;}continue;
- }
- bfs_back();
- }
- }
- int main()
- {
- cin >> s_start;Node now;now.s = s_start; now.step = 0;Q1.push(now);
- now.s = s_end;Q2.push(now);
- bfs_front();
- return 0;
- }
- //283104765
- //273645801
- //15
- //103824765
- //120843765
- //123805746
来源: http://www.bubuko.com/infodetail-2357730.html