剑指offer12矩阵中的路径刷题打卡
剑指offer12
深度优先遍历做法：
思路：
确定起始位置，从起始位置开始，扫描上下左右位置是否可以前进（isValid函数），可以前进则前进至直到路径包含完毕。
解题：
工具函数
isvalid函数
一个isvalid函数，判断遍历到的位置是否符合正确路径的值
bool isValid(string word, int ptr, char value){if(word[ptr] == value) return true;return false;
}// 调用形式
isValid(isValid(word, ptr, board[i][j]));
- 需要注意的是在每次判断之前，
ptr位置前面的值一定是正确的，因为是逐个判断和遍历过来的
findFirst函数
这个函数是用来保存board中word第一个字符的位置，因为可能有很多个，所以我使用unordered_map来保存
void findFirst(vector<vector<char>>& board, char word, unordered_map<int, pair<int, int>>& firstword){// 查找word起始字符的位置int count = 0;for(int i = 0; i <board.size(); i++){for(int j = 0; j <board[0].size(); j++){if(board[i][j] == word) firstword.insert(pair<int, pair<int, int>>(count++, make_pair(i, j)));}}
}
- 其中泛型为
<int, pair<int, int>>，其中key值仅仅用于标识唯一的位置，没有用mutimap所以如果使用<int, int>，就会出现如果两个位置是[3, 0]、[3, 2]这样其中一个值就会被覆盖掉
主函数与深度优先函数
exist函数
题解中的主函数，用于初始化与驱动回溯函数
bool exist(vector<vector<char>>& board, string word) {vector<vector<int>> used(board.size(), vector<int>(board[0].size(), 0)); // 与board大小相同的条件数组unordered_map<int, pair<int, int>> firstword; // 存放所有起始位置的集合findFirst(board, word[0], firstword); // 查找并保存起始位置元素集合的位置for(auto i: firstword){ // 试着从每一个起始位置开始深度优先遍历查找if(backtracking(board, word, i.second.first, i.second.second, 0, used)) return true;}return false;
}
- 第一个是
used数组，大小与board数组一样，主要作用是防止走倒路，后面会解释 - 第二个是
firstwordmap映射集合，用来存放所有起始位置的集合 - 第三个是
findFirst函数，用于查找找并保存起始位置元素集合的位置 - 接着就是尝试从每一个起始位置开始深度优先搜索
backtracking函数
递归三步：
-
确定参数和返回值
-
除了
exist中的两个参数之外还需要添加当前位置参数(int i, int j)，和遍历到了word中的那哪个位置(int ptr)，和一个防止走倒路的数组(vector<vector<int>>& used) -
返回值是
bool，只要找到一条合适的路径直接返回true即可bool backtracking(vector<vector<char>>& board, string word, int i, int j, int ptr, vector<vector<int>>& used );
-
-
确定终止条件
-
当
ptr遍历到word.size() - 1时并且该位置与其最后一个位置的字符是相同的则返回trueif(ptr == word.size() - 1 && board[i][j] == word[ptr]) return true;
-
-
确定本层逻辑
-
大致框架
bool backtracking(vector<vector<char>>& board, string word, int i, int j, int ptr, vector<vector<int>>& used ){if(ptr == word.size() - 1) return true;if(isValid(word, ptr, board[i][j])){// 左// 下// 右// 上} } -
以这个框架展开讲解，首先要是确保当前值是有效的（是在路径上并且对应的位置也相同），然后开始遍历
if(backtracking(board, word, i, j + 1, ptr + 1,used)) return true; if(backtracking(board, word, i + 1, j, ptr + 1,used)) return true; if(backtracking(board, word, i, j - 1, ptr + 1,used)) return true; if(backtracking(board, word, i - 1, j, ptr + 1,used)) return true;以第一个作为讲解，开始往右遍历也就是
j+1然后ptr+1判断右侧值是否有效，这里就有回溯，回溯在于ptr+1与j+1，在函数执行完毕后，j的值不会变，也就进行了一次回溯然后继续查看下方合适吗，在这一过程中，只要找到了合适的路，直接返回，不会后面的递归。边界判断：
-
既然对
i和j上有操作，那么就一定要判断是否越界if(j + 1 < colSize) if(backtracking(board, word, i, j + 1, ptr + 1,used)) return true; if(i + 1 < rowSize) if(backtracking(board, word, i +1, j, ptr + 1,used)) return true; if(j - 1 >= 0) if(backtracking(board, word, i, j - 1, ptr + 1,used)) return true; if(i - 1 >= 0) if(backtracking(board, word, i - 1, j, ptr + 1,used)) return true;在执行
isvalid前获取colsize与rowsize这样整体的代码会是这样bool backtracking(vector<vector<char>>& board, string word, int i, int j, int ptr, vector<vector<int>>& used){if(ptr == word.size() - 1) return true;int rowSize = board.size();int colSize = board[0].size();if(isValid(word, ptr, board[i][j])){if(j + 1 < colSize) if(backtracking(board, word, i, j + 1, ptr + 1)) return true; if(i + 1 < rowSize) if(backtracking(board, word, i +1, j, ptr + 1)) return true; if(j - 1 >= 0) if(backtracking(board, word, i, j - 1, ptr + 1)) return true; if(i - 1 >= 0) if(backtracking(board, word, i - 1, j, ptr + 1)) return true; }return false; }运行测试用例发现很开心过了
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FVLwAhDZ-1681874766177)(image\\image-20230419111229004.png)]
于是屁颠屁颠的提交
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fOPjnaFk-1681874766178)(image\\image-20230419111304192.png)]
后来根据打日志调试，发现是他走了倒路！
这个测试用例长这样
A B C E S F C S A D E E 这版代码他会按照
[0,0] -> [0, 1] -> [0, 2] -> [0, 3] -> [1 , 2] -> [0, 2]这样走，你就会发现他走了倒路，于是这就要用上我们的最后一个参数used数组，加入之后代码大框架的变化会是这样bool backtracking(vector<vector<char>>& board, string word, int i, int j, int ptr, vector<vector<int>>& used ){if(used[i][j] == 1) return false;if(ptr == word.size() - 1 && board[i][j] == word[ptr]) return true;used[i][j] = 1;if(isValid(word, ptr, board[i][j])){// 左// 下// 右// 上}used[i][j] = 0;return false; }这样一来他就不会在
[0,0] -> [0, 1] -> [0, 2] -> [0, 3] -> [1 , 2] -> [0, 2]这条路中走最后一个结点，因为我们使用了一个used数组避免了走倒路
-
-
完整代码：
class Solution {
public:bool isValid(string word, int ptr, char value){if(word[ptr] == value) return true;return false;}bool backtracking(vector<vector<char>>& board, string word, int i, int j, int ptr, vector<vector<int>>& used){if(used[i][j] == 1) return false;if(ptr == word.size() - 1 && board[i][j] == word[ptr]) return true;int rowSize = board.size();int colSize = board[0].size();used[i][j] = 1;if(isValid(word, ptr, board[i][j])){ // 如果该值可以则深度优先if(j + 1 < colSize) if(backtracking(board, word, i, j + 1, ptr + 1,used)) return true; if(i + 1 < rowSize) if(backtracking(board, word, i +1, j, ptr + 1,used)) return true; if(j - 1 >= 0) if(backtracking(board, word, i, j - 1, ptr + 1,used)) return true; if(i - 1 >= 0) if(backtracking(board, word, i - 1, j, ptr + 1,used)) return true; }used[i][j] = 0;return false;}void findFirst(vector<vector<char>>& board, char word, unordered_map<int, pair<int, int>>& firstword){int count = 0;for(int i = 0; i <board.size(); i++){for(int j = 0; j <board[0].size(); j++){if(board[i][j] == word) firstword.insert(pair<int, pair<int, int>>(count++, make_pair(i, j)));}}} bool exist(vector<vector<char>>& board, string word) {vector<vector<int>> used(board.size(), vector<int>(board[0].size(), 0));unordered_map<int, pair<int, int>> firstword;findFirst(board, word[0], firstword);for(auto i: firstword){cout<<"i = "<<i.second.first<< "; j = "<<i.second.second<<endl;if(backtracking(board, word, i.second.first, i.second.second, 0, used)) return true;}return false;}
};
当然对于边界的判断可以放在最开始
bool backtracking(vector<vector<char>>& board, string word, int i, int j, int ptr, vector<vector<int>>& used){// 边界判断int rowSize = board.size();int colSize = board[0].size();if(j >= colSize || i >= rowSize || j < 0 || i < 0) return false;if(used[i][j] == 1) return false; // 防止走倒路if(ptr == word.size() - 1 && board[i][j] == word[ptr]) return true; // 路径长度已经符合并且是目标路径// 标记当前结点已经访问used[i][j] = 1;// 开始深度优先搜索 分为上下左右移动搜索 我根据示意图 按照右 下 左 上的顺序遍历if(isValid(word, ptr, board[i][j])){ // 如果当前位置符合可以则进行深度优先if(backtracking(board, word, i, j + 1, ptr + 1,used)) return true; if(backtracking(board, word, i + 1, j, ptr + 1,used)) return true; if(backtracking(board, word, i, j - 1, ptr + 1,used)) return true; if(backtracking(board, word, i - 1, j, ptr + 1,used)) return true; }used[i][j] = 0;return false;
}
