网站建设的毕业设计报告,餐饮品牌策划,sem论坛,全媒体广告代理加盟矩阵中的路径#xff08;回溯#xff09;/pair的学习问题分析示例代码pair学习问题
来自力扣#xff1a;
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
单词必须按…
矩阵中的路径回溯/pair的学习问题分析示例代码pair学习问题
来自力扣
给定一个 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提示
m board.length
n board[i].length
1 m, n 6
1 word.length 15
board 和 word 仅由大小写英文字母组成分析
这题型很明显就是回溯。定义一个查找函数然后递归调用。最近被一些别的事困扰没心思自己写偷懒直接看示例代码了。
示例代码
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;} else 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]) {bool flag check(board, visited, newi, newj, s, k 1);if (flag) {result true;break;}}}}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));for (int i 0; i h; i) {for (int j 0; j w; j) {bool flag check(board, visited, i, j, word, 0);if (flag) {return true;}}}return false;}
};
官方的解释
pair学习
代码中有pair这让我回想起之前用map的时候好像用过pair但并不了解它。 学习内容参考这两篇C pair的基本用法总结整理和老卫带你学—C中map与pair的区别
pair将2个数据组成一对数据。它是结构体不是类。即它是同struct定义的。 使用前需要include一个头文件#includeutility 模板templateclass T1,class T2 struct pair 定义和访问(用公有函数first和sencond访问) pairint, int a { 1,5 };pairint, int b( 1,5 );pairint, int c make_pair(1, 5);cout a.first a.second ;cout b.first b.second ;cout c.first c.second ;//结果1 5 1 5 1 5与map的区别map是容器pair可以生成一个一个的pair然后放入容器map中。
同样的pair定义的变量可以用其他容器如vector来存放。
