力扣773：滑动谜题

力扣773：滑动谜题

https://leetcode.cn/problems/sliding-puzzle/description/
代码内容：

1. class Solution {
2. public:
3.     int slidingPuzzle(vector<vector<int>>& board) {
4.         string start="";
5.         for(int i = 0;i<2;i++)
6.         {
7.             for(int j = 0;j<3;j++)
8.             {
9.                 start.push_back(board[i][j]+'0');
10.             }
11.         }
12.         string target = "123450";
13.         //将二维数组压缩为一维数组的索引，以0所在位置
14.         vector<vector<int>> index{
15.             {1,3},
16.             {0,4,2},
17.             {1,5},
18.             {0,4},
19.             {3,1,5},
20.             {4,2}
21.         };
22.         //BFS
23.         queue<string> q;
24.         q.push(start);
25.         unordered_set<string> visited;
26.         visited.insert(start);
28.         int step = 0;
29.         while(!q.empty())
30.         {
31.             int size = q.size();
32.             for(int i = 0;i<size;i++)
33.             {
34.                 string cur = q.front();
35.                 q.pop();
36.                 //如果这个是目标值，直接返回
37.                 if(cur == target)
38.                     return step;
39.             
40.             
41.                 //如果不是，查找对应的索引
42.                 int ind;
43.                  for(ind = 0;cur[ind]!='0';ind++);
44.                  //查到0的位置，后根据位置进行各个方向交换
45.                 for(int a:index[ind])
46.                 {
47.                     string new_board = cur;
48.                     swap(new_board[ind],new_board[a]);
49.                     //防止重复，缩小时间复杂度
50.                     if(!visited.count(new_board))
51.                     {
52.                         q.push(new_board);
53.                         visited.insert(new_board);
54.                     }
55.                 }
56.             }
57.             step++;
58.         }
59.         return -1;
60.     }
61.    
62. };

复制代码

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 界说为选择 0 与一个相邻的数字（上下左右）进行互换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
这个题目主要就是暴力穷举的做法，将二维数组压缩为一维数组，用广度优先：
我们起首创建两个string类型，保存target和start,而我们的二维数组是int类型，所以我们需要先转换为string,通过将int+'0'来将数字转换为对应的字符.尚有一个难点就是将二维数组压缩为一维数组后，一维数组怎么表示二维数组，我们这里利用了一个索引
[code][/code] vector<vector<int>> index{ {1,3}, {0,4,2}, {1,5}, {0,4}, {3,1,5}, {4,2} };
这个索引，主要表示'0'在6个差别位置，他可能互换的地方。例如：012345对应的下标为012345,即

0	1	2
3	4	5

我们此时的'0'在一维数组的0号下标,因此，我们进行互换可以向右互换，向下互换，即互换的索引就是1,3;
然后我们通过string类型的队列，一个一个广度搜索比较.

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。