Day14 2022.11.20 搜索与回溯算法（中等）
12.矩阵中的路径
自己实现
总体就是进行递归，递归函数最后向四个方向递归，为保证在同一个起点的可能路径递归中不重复走之前的路径，设置了一个标记数组int mark[][]。
递归出口：
- 如果下标越界数组，return false
- 如果该点已被标记，return false
- 如果该点与
word中对应位置的字符相等&&是word最后一个字符了，return true - 如果该点字符与
word对应位置字符不相等，则取消该点标记并return false
同时，每一次从不同的顶点出发时，要清空mark中所有标记。
代码如下：
class Solution {
int len_word;
vector<vector<int>> mark;
public:
bool exist(vector<vector<char>>& board, string word) {
len_word = word.length();
vector<int> tmp(board[0].size());
for (int i = 0; i < board.size(); i++)mark.push_back(tmp);
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[0].size(); j++)
{
if (!mark[i][j])
{
if (recur(board, word, i, j, 0))return true;
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[0].size(); j++)
{
mark[i][j] = 0;
}
}
}
}
}
return false;
}
bool recur(vector<vector<char>>& board, string word, int i, int j, int k)
{
if (i == -1 || i == board.size() || j == -1 || j == board[0].size())return false;
if (mark[i][j] == 1)return false;
mark[i][j] = 1;
if (board[i][j] == word[k] && k == word.size() - 1)return true;
if (board[i][j] != word[k])
{
mark[i][j]=0;
return false;
}
if (recur(board, word, i, j + 1, k + 1) || recur(board, word, i + 1, j, k + 1) || recur(board, word, i - 1, j, k + 1) || recur(board, word, i, j - 1, k + 1))return true;
mark[i][j] = 0;
return false;
}
};
代码表现
题解
和自己实现差不多，只是将34行判断合并到30行中了，同时就可以取消33行判断中的board[i][j]==word[k]
hint：
- debug很久的原因主要都在
mark[i][j]的清除，只有因为处于该路径下的该点不符合return false时才要清除，而如果时因为该点有标记return false则不需要清除 vector<int> vec(3)可以规定vec的capacity，但是如果想对vec[0]赋值，则不能用vec.push_back()了- 注意递归出口的顺序问题
13.机器人的运动范围
自己实现
和上一个题类似，也是用递归来做，用到了标记数组mark[][]。但需要注意的一个条件是，这个题目是从[0][0]开始走，所以不存在换起点的说法。
递归出口：
-
如果下标越界数组，return false
-
如果该点已经被标记（走过），return false
如果通过了，这个时候对这个点进行标记
-
如果这个点下标满足各数位之和 ＞ k的话，return false
通过上述出口，再将计数器
cnt++
但是！因为这个题是统计符合条件的点的个数，所以不需要换起点，也不需要重置标记数组。
代码如下：
class Solution {
int cnt;
vector<vector<int>> mark;
public:
int movingCount(int m, int n, int k) {
cnt=0;
vector<int> tmp(n);
for(int i=0;i<m;i++)mark.push_back(tmp);
recur(m,n,0,0,k);
return cnt;
}
bool recur(int m,int n,int i,int j,int k)
{
if(i<0||i>=m||j<0||j>=n)return false;
if(mark[i][j])return false;
mark[i][j]=1;
if(!cal(i,j,k))
{
mark[i][j]=1;
return false;
}
cnt++;
recur(m,n,i,j+1,k);
recur(m,n,i+1,j,k);
recur(m,n,i,j-1,k);
recur(m,n,i-1,j,k);
return true;
}
bool cal(int a,int b,int k)
{
int sum=0;
while(a!=0)
{
sum+=a%10;
a/=10;
}
while(b!=0)
{
sum+=b%10;
b/=10;
}
if(sum<=k)return true;
else return false;
}
};
代码表现
题解
1. DFS深度优先搜索
具体见自己实现，是一样的
2. BFS广度优先搜索
用队列来实现，通过出队并将下方和右方的元素入队来实现广度优先搜索同步往前推进的效果。其余部分（判断、标记）和DFS是一样的，不再赘述，直接贴上题解代码
代码如下
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> visited(m, vector<bool>(n, 0));
int res = 0;
queue<vector<int>> que;
que.push({ 0, 0, 0, 0 });
while(que.size() > 0) {
vector<int> x = que.front();
que.pop();
int i = x[0], j = x[1], si = x[2], sj = x[3];
if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
visited[i][j] = true;
res++;
que.push({ i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
que.push({ i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
}
return res;
}
};
代码表现
时间好像有点离谱……应该是数据问题
