剑指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时并且该位置与其最后一个位置的字符是相同的则返回true
if(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; }
