剑指Offer12.矩阵中的路径 C++

1、题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true
示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false

2、VS2019上运行

使用回溯的方法

#include <iostream>
#include <vector>
using namespace std;class Solution {
public:bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {// 检查当前坐标的字母是否与目标单词中的对应字母相等if (board[i][j] != s[k]) {return false;}// 如果已经匹配到目标单词的最后一个字母，表示找到了路径，返回trueelse if (k == s.length() - 1) {return true;}visited[i][j] = true; // 将当前坐标标记为已访问vector<pair<int, int>> directions{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; // 上、下、左、右四个方向bool result = false; // 用于记录是否找到路径// 依次遍历四个方向for (const auto& dir : directions) {int newi = i + dir.first, newj = j + dir.second; // 计算新坐标// 检查新的坐标是否在矩阵范围内且没有被访问过if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {if (!visited[newi][newj]) {//用于检查位置(newi, newj)是否已经被访问过// 递归调用check函数进行下一步的搜索bool flag = check(board, visited, newi, newj, s, k + 1);if (flag) {result = true; // 如果找到路径，直接返回truebreak;}}}}visited[i][j] = false; // 撤销对当前坐标的标记return result;}bool exist(vector<vector<char>>& board, string word) {int h = board.size(), w = board[0].size(); // 矩阵的行数和列数vector<vector<int>> visited(h, vector<int>(w)); // 记录每个格子的访问状态// 遍历矩阵的每个格子，对每个格子调用check函数for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {bool flag = check(board, visited, i, j, word, 0); // 调用check函数进行搜索if (flag) {return true; // 如果找到路径，直接返回true}}}return false; // 遍历结束后仍未找到路径，返回false}
};int main() {// 示例用法vector<vector<char>> board = {{'A', 'B', 'C', 'E'},{'S', 'F', 'C', 'S'},{'A', 'D', 'E', 'E'}};Solution s;string word = "ABCCED";if (s.exist(board, word)) {cout << "Word exists in the board." << endl;}else {cout << "Word does not exist in the board." << endl;}return 0;
}

Word exists in the board.

3、整体思路

整体的思路是使用深度优先搜索（DFS）算法在矩阵中搜索是否存在与目标单词匹配的路径。

• 首先，定义一个 check 函数来进行递归的搜索。该函数接收当前的坐标 (i, j)、目标单词 s、以及目前匹配的字符索引 k。函数的返回值是一个布尔值，表示是否找到了匹配的路径。
• 在 check 函数中，首先进行边界条件的判断。如果当前索引 k 已经匹配到目标单词的最后一个字符，说明已经找到了匹配的路径，返回 true。
• 接下来，检查当前坐标 (i, j) 处的字母是否与目标单词中的对应字母相等。如果不相等，说明当前路径匹配失败，返回 false。
• 检查新坐标是否在矩阵的范围内，并且该位置没有被访问过（即 visited[newi][newj] = false）。
  如果满足上述条件，则递归调用 check 函数，在新坐标 (newi, newj) 上继续匹配下一个字符，即 k + 1。
• 如果递归调用返回 true，表示在某个方向上找到了匹配的路径，直接返回 true。
  如果所有方向的递归调用都没有找到匹配的路径，则撤销对当前坐标 (i, j) 的标记，将 visited[i][j] 设置为 false，表示可以重新访问该位置。
• 最后，如果所有方向都探索完毕，仍然没有找到匹配的路径，则返回 false，表示没有找到路径。
• 接下来可以调用 check 函数，从矩阵的每个位置出发，判断是否存在与目标单词匹配的路径。如果返回 true，则说明存在这样的路径；如果返回 false，则说明不存在。
• 这就是整体的思路，通过DFS算法搜索矩阵中的路径，并利用递归和回溯的思想进行搜索和撤销标记。

4、int h = board.size(), w = board[0].size();

• 这行代码int h = board.size(), w = board[0].size();的作用是获取二维字符向量board的行数h和列数w。
• 1.board.size()返回二维字符向量board的行数，即向量中包含的子向量个数。
  2.board[0].size()返回二维字符向量board中第一行子向量的列数，假设矩阵不为空。

5、vector<vector> visited(h, vector(w));

• 这行代码vector<vector<int>> visited(h, vector<int>(w));创建了一个名为visited的二维整数向量，其大小与输入矩阵board的行数和列数相同。
• 1.vector<int>(w)部分创建了一个大小为w的整数向量。
• 2.vector<vector<int>> visited(h, vector<int>(w));使用上述创建的子向量为每一行创建了一个整数向量，从而形成了一个大小为h行、w列的二维整数向量visited。
• 这样的二维向量visited可以用于跟踪和记录在处理board矩阵时已经访问过的位置或标记。

6、dir.first 和dir.second

• dir.first表示dir这个pair（键值对）中的第一个元素，即表示方向的行坐标变化。在该上下左右的方向向量中，dir.first表示上下移动的行坐标的变化量。
• 例如，如果dir是(-1, 0)，那么dir.first就是-1，表示向上移动1行。同理，如果dir是(1, 0)，那么dir.first就是1，表示向下移动1行。
• 在搜索一个矩阵的周围方向时，dir.first的值用于计算新的行坐标。通过将当前位置的行坐标i与dir.first相加，可以得到新的行坐标，用于在矩阵中检查相邻位置是否符合要求。

7、visited[i][j] = false;

• 这行代码为撤销对当前坐标(i, j)的访问标记，将其重新设置为false。
• 标记的目的是为了跟踪遍历矩阵时已经访问过的位置，以避免重复访问。在代码中，visited向量用于标记位置是否已经被访问过。
• 当程序进行完成对位置(i, j)的处理后，如果希望在后续的搜索或迭代中能够重新访问该位置，就需要撤销对该位置的访问标记，将visited[i][j]重新设置为false。
• 撤销对当前坐标的标记允许在后续的遍历或搜索过程中重新考虑访问该位置，以发现其他可能的路径或结果。如果不撤销标记的话，可能会导致某些位置被错误地标记为已访问，从而错过了找到其他路径或结果的机会。因此，需要在适当的时候撤销对当前坐标的标记。

8、for (const auto& dir : directions)

• for (const auto& dir : directions) 是一个范围-based的循环语句，用于遍历容器 directions 中的元素。
• 在这个语句中，dir 是一个临时变量，它会依次取到 directions 中的每个元素值。关键字 auto 会自动推断 dir 的类型，使其与 directions 中的元素类型保持一致。const 修饰符表示 dir 是一个常量，即在循环体内不能对它进行修改。
• 通过这个循环语句，可以依次遍历 directions 容器中的每个方向，执行相应的操作，如计算新坐标 (newi, newj)，进行路径匹配等。这样可以依次尝试不同的方向，以搜索矩阵中是否存在与目标单词匹配的路径。