C++刷LeetCode（773. 滑动谜题）【广度优先搜索】

糖逗

题目描述：

1. 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
   
2. 
   
3. 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
   
4. 
   
5. 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
   
6. 
   
7. 给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
   
8. 
   
9. 示例：
   
10. 
    
11. 输入：board = [[1,2,3],[4,0,5]]
    
12. 输出：1
    
13. 解释：交换 0 和 5 ，1 步完成
    
14. 输入：board = [[1,2,3],[5,4,0]]
    
15. 输出：-1
    
16. 解释：没有办法完成谜板
    
17. 输入：board = [[4,1,2],[5,0,3]]
    
18. 输出：5
    
19. 解释：
    
20. 最少完成谜板的最少移动次数是 5 ，
    
21. 一种移动路径:
    
22. 尚未移动: [[4,1,2],[5,0,3]]
    
23. 移动 1 次: [[4,1,2],[0,5,3]]
    
24. 移动 2 次: [[0,1,2],[4,5,3]]
    
25. 移动 3 次: [[1,0,2],[4,5,3]]
    
26. 移动 4 次: [[1,2,0],[4,5,3]]
    
27. 移动 5 次: [[1,2,3],[4,5,0]]
    
28. 输入：board = [[3,2,4],[1,5,0]]
    
29. 输出：14
    
30. 提示：
    
31. 
    
32. board 是一个如上所述的 2 x 3 的数组.
    
33. board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/sliding-puzzle
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int slidingPuzzle(vector<vector<int>>& board) {
   
4.         string start = "";
   
5.         int len1 = board.size(), len2 = board[0].size();
   
6.         for (int i = 0; i < len1; i++) {
   
7.             for (int j = 0; j < len2; j++) {
   
8.                 start.push_back(board[i][j] + '0');
   
9.             }
   
10.         }
    
11.         /*
    
12.         012
    
13.         345         
    
14.         */
    
15.         string end = "123450";
    
16.         vector<vector<int> >neighbors = {
    
17.             {1, 3},
    
18.             {0, 2, 4},
    
19.             {1, 5},
    
20.             {0, 4},
    
21.             {1, 3, 5},
    
22.             {2, 4}
    
23.         };
    
24.         //广度优先搜索
    
25.         queue<string>store;
    
26.         set<string>visit;
    
27.         store.push(start);
    
28.         visit.insert(start);
    
29.         int res = 0;
    
30.         while(!store.empty()){
    
31.             int len = store.size();
    
32.             for(int i = 0; i < len; i++){
    
33.                 string temp = store.front();
    
34.                 store.pop();
    
35.                 if(temp == end)return res;
    
36.                 //找到当前string中0的位置
    
37.                 int index;
    
38.                 for(index = 0; index < temp.size(); index++){
    
39.                     if(temp[index] == '0')break;
    
40.                 }
    
41.                 //将当前0与其邻居交换
    
42.                 for(auto cha : neighbors[index]){
    
43.                     string cur = temp;
    
44.                     swap(cur[index], cur[cha]);
    
45.                     if(visit.count(cur) == 0){
    
46.                         store.push(cur);
    
47.                         visit.insert(cur);
    
48.                     }
    
49.                 }
    
50.             }
    
51.             res++;
    
52.         }
    
53.         return -1;
    
54.     }
    
55. };

复制代码

参考链接：https://leetcode-cn.com/problems ... i-zhi-you-xi-by-la/