BFS+DFS终结游戏题目
BFS+DFS终结游戏题目
1.开篇
本节主要阐述BFS+DFS快速完成相关题目，以LeetCode773为例。
773. 滑动谜题 https://leetcode-cn.com/problems/sliding-puzzle/
题目描述：在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成解决这道题比较关键的几点：
- 0与周围位置交换后得到一个新的二维矩阵，如果以二维矩阵存储开销太大，BFS中queue与visited中不方便存储。
- 如何保证结点被访问过，这里使用一个set即可。
2.BFS
为了简单起见，我们将二维转一维度，一维转二维做个简单介绍。
1 2 3
4 5 0针对上述这个二维矩阵，例如0的位置是(1,2)，放在一维就是3*1+2=5。
一维：
1 2 3 4 5 00所在位置是5，转为二维便是x=5/3=1 y=5%3=2,也就是(1,2)。
下面开始正文，本题的结构这样，以[[1,2,3],[4,0,5]]为例：
123405
123045 123450 103425
............................实际上就是多叉树，类似层次遍历，不断入队，出队，当碰到第一个字符串与目标串123450相等的时候，便是最少的交换次数。
先写一个转string的函数：
string boardToString(const vector<vector<int>>& board) {
string res="";
for (auto elem : board)
for (auto e : elem) res+=to_string(e);
return res;
} 随后，定义二维矩阵的上下左右方向数组及二维矩阵的维度，是否越界函数
private:
int d[4][2] = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
int n,m;
public:
bool inBoard(int x,int y) {
return x>=0&&x<n&&y>=0&&y<m;
}我们开始入队的一些操作：
string start = boardToString(board);
int step = 0;
unordered_set<string> visited;
queue<string> q;
q.push(start);
visited.insert(start);对应到上述多叉树，便是123405作为start结点入队，并标记访问过。
随后就是：
while(!q.empty()) {
// dosomething
}每一层我们看到是多个结点，因此我们一层层处理，需先拿到q的size，随后不断出队列，将节点进行上下左右方向交换，并判断是否满足条件及是否被访问过：
while(!q.empty()) {
int sz = q.size();
for (int i=0;i<sz;i++) {
string cur = q.front();
q.pop();
if (cur == "123450") return step;
int index = cur.find('0'); // 类似一维数组的index
int x=index/m; // 一维转二维x
int y=index%m;
// 方向变换
for (int j=0;j<4;j++) {
int x1 = x+d[j][0];
int y1 = y+d[j][1];
if(inBoard(x1,y1)) {
string tmp = cur;
swap(tmp[index],tmp[x1*m+y1]);
if(!visited.count(tmp)) {
q.push(tmp);
visited.insert(tmp);
}
}
}
}
step++;
}比较重要的一点是：
if(inBoard(x1,y1)) {
string tmp = cur;
swap(tmp[index],tmp[x1*m+y1]);
if(!s.count(tmp)) {
q.push(tmp);
s.insert(tmp);
}
}这里表示先拷贝一份原字符串，针对拷贝的字符串进行swap操作，这样下次还是针对原数组进行交换，比较方便，随后入队并标记，跟root结点一样。
3.DFS
这道题使用DFS做，容易TLE，例如：下面这样形成环，假设我们想得到从a->d的最短长度，进行DFS扫描的时候a>b->c->d这条路径被访问了，下次访问另一条a->d，到d的时候被访问过了，直接就退出了，因此得不到想要的路径，怎么办呢？我们目的是让他进入比原先a->b->c->d更短的路径，不断的回溯每一条路径，直到找到最短的，那么短还是长需要被纪录，同时该点是否被访问也需要纪录，因此我们这里不能只用一个set来保存了，需要使用一个map或unordered_map，将查询的信息作为key，value为该key对应的长短信息。
a
/ \
b d
\ /
c下面具体定义一下：
private:
int d[4][2] = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
int n,m;
unordered_map<string,int> um;
int ret;
public:
int slidingPuzzle(vector<vector<int>>& board) {
n = board.size();
m = board[0].size();
ret = INT_MAX;
string start = boardToString(board);
um = unordered_map<string,int>();
dfs(start,0);
return ret == INT_MAX ? -1 : ret;
} 随后就是我们的dfs：
dfs出口：当前交换次数已经大于最短交换次数，或者该结点被之前访问的时候比现在访问要短(交换次数少)，直接退出即可。抵达目标，获取最小值，退出。
if (ans > ret || (um[s] != 0 && um[s] <= ans)) return ;
if (s == "123450") {
ret = min(ret, ans);
return;
}最后就是dfs要做的事：
int index = s.find('0');
int x=index/m;
int y=index%m;
um[s] = ans; // visited 更新
for (int j=0;j<4;j++) {
int x1 = x+d[j][0];
int y1 = y+d[j][1];
if(inBoard(x1,y1)) {
swap(s[index],s[x1*m+y1]);
dfs(s,ans+1);
swap(s[x1*m+y1],s[index]); // 回溯
}
}
return;本节完~