大背景类型的网站设计,品牌的网站建设一般多少钱,手机网页游戏排行榜前十名,内力网站建设1、题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平…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(vectorvectorchar board, vectorvectorint 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; // 将当前坐标标记为已访问vectorpairint, 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(vectorvectorchar board, string word) {int h board.size(), w board[0].size(); // 矩阵的行数和列数vectorvectorint visited(h, vectorint(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() {// 示例用法vectorvectorchar 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、vectorvector visited(h, vector(w));
这行代码vectorvectorint visited(h, vectorint(w));创建了一个名为visited的二维整数向量其大小与输入矩阵board的行数和列数相同。1.vectorint(w)部分创建了一个大小为w的整数向量。2.vectorvectorint visited(h, vectorint(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)进行路径匹配等。这样可以依次尝试不同的方向以搜索矩阵中是否存在与目标单词匹配的路径。
