蓝桥杯卡片换位(bfs)

卡片换位

你玩过华容道的游戏吗？
这是个类似的，但更简单的游戏。
看下面 3 x 2 的格子

在其中放5张牌，其中A代表关羽，B代表张飞，* 代表士兵。
还有一个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入格式：
输入两行6个字符表示当前的局面

输出格式：
一个整数，表示最少多少步，才能把AB换位（其它牌位置随意）

例如，输入：

程序应该输出：
17

再例如，输入：

程序应该输出：
12

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

解题过程：

这道题一开始用bfs的时候发现结果怎么也不对，找了很久发现自己写的是其他字符位置不变，只是A和B互换位置为bfs的返回条件。

之后看了一下题，发现A和B互换位置即可，其他字符的位置随便怎么样都行。。所以以后做题的时候一定要认真审题，不要急躁。

思路：用一个string保存每一个局面的状态，图中的数字表示string的下标i，当i-1，i+1，i-3，i+3分别表示向左，向右，向上，向下走。使用set对该局面(string)进行判重。

但是注意到用如下的图有限制，比如3-1 = 2，但是3和2并不相邻。

所以将每一个局面的状态的保存修改为如下string，string的下标3不使用(代码中将其赋予了#)，此时i-1，i+1，i-4，i+4分别表示向左，向右，向上，向下走，这样就消除了边界的影响。

 1 #include<iostream>
 2 #include<string>
 3 #include<queue>
 4 #include<set>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<stdio.h>
 9 
10 using namespace std;
11 
12 int dx[4] = {1,-1,4,-4};
13 
14 string start_str;
15 int orig_posA;
16 int orig_posB;
17 
18 struct node
19 {
20     int x;    // 空格字符所在的下标
21     string str;
22     int step;
23 };     
24 
25 void bfs(node nod)
26 {
27     queue<node> Q; 
28     Q.push(nod);
29     set<string> sset;
30     sset.insert(nod.str);
31     
32     node t, p;
33     while(!Q.empty())
34     {
35         t = Q.front();
36         Q.pop();
37         
38         /* 一开始把判断条件错误地写成了 if(t.str == end_str), end_str表示把
39             初始字符串中A,B位置互换后的字符串， 但是这样也把其他字符的位置固定死了 */
40         // 正解：A和B的位置与一开始的位置互换即可，其他字符的位置随意 
41         if(t.str.find('B') == orig_posA && t.str.find('A') == orig_posB)
42         {
43             cout << t.step << endl;
44             return;
45         } 
46         
47         
48         for(int i = 0; i < 4; ++i)
49         {
50             int xx = t.x + dx[i];
51             if((xx >= 0 && xx <= 2) || (xx >= 4 && xx <= 6))
52             {
53                 string ss = t.str;
54                 swap(ss[t.x], ss[xx]);
55                 p.x = xx;
56                 p.str = ss;
57                 p.step = t.step + 1;
58                 if(sset.count(p.str) == 0)
59                 {
60                     sset.insert(p.str);
61                     Q.push(p);
62                 }
63                  
64             }
65         }
66     }
67     
68 }
69 
70 int main()
71 {
72     string s1;
73     string s2;
74     getline(cin, s1);
75     getline(cin, s2);
76     
77     // 下标3不使用，此处将其赋值为了# 
78     start_str = s1 + '#' + s2;
79     
80     int start_x = start_str.find(' '); 
81     orig_posA = start_str.find('A');
82     orig_posB = start_str.find('B');
83     
84     node nod;
85     nod.x = start_x;
86     nod.str = start_str;
87     nod.step = 0;
88     bfs(nod);
89     
90     
91     
92     return 0;
93 }

蓝桥杯 卡片换位(bfs)

蓝桥杯卡片换位(bfs)