剑指Offer12-矩阵中的路径 题目描述

思路分析

显然这是一个深度优先搜索的题，遍历整个矩阵寻找word的首字母，然后对首字母位置的上下左右四个方向进行延展，判断第二个字母是否存在，依此方法直到找到整个word字符串，即为true。为了避免重复遍历某个位置，在一条分支走过该位置时将其置为数字等不影响的字符作为标记，由于不同分支互不影响，所以在该分支结束时需要将标记恢复。

代码

bool exist(vector<vector<char>>& board, string word) {int row = board.size(), col = board[0].size();for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (dfs(i, j, board, word, 0)) {return true;}}}return false;}bool dfs(int i, int j, vector<vector<char>>& board, string word, int wordIndex) {int row = board.size(), col = board[0].size();if (wordIndex == word.size()) {return true;}if (i < 0 || i >= row || j < 0 || j >= col) {return false;}bool res = false;if (board[i][j] == word[wordIndex]) {board[i][j] = '1';//标记走过的分支res = dfs(i + 1, j, board, word, wordIndex + 1) || dfs(i - 1, j, board, word, wordIndex + 1) || dfs(i, j + 1, board, word, wordIndex + 1) || dfs(i, j - 1, board, word, wordIndex + 1);board[i][j] = word[wordIndex];//将标记恢复}return res;}

剑指Offer13-机器人的运动范围径 题目描述

思路分析

因为是找到所有可达到的方格，所以可以用深度优先和广度优先进行搜索。使用深度优先与上题步骤基本一样，只是判定满足要求的条件不同，并且每个符号要求的方格只记录一次，所以标记过方格后无需恢复。

代码

int movingCount(int m, int n, int k) {vector<vector<int>> signedMap(m, vector<int>(n));int count = 0;moveOne(m, n, signedMap, 0, 0, count, k);return count;}//深度优先搜索void moveOne(int m, int n, vector<vector<int>>& signedMap, int x, int y, int& count, int k){if(x < 0 || x >= m || y < 0 || y >= n || signedMap[x][y] != 0 || (getSum(x) + getSum(y) > k)){return;}count++;signedMap[x][y] = -1;moveOne(m, n, signedMap, x - 1, y, count, k);moveOne(m, n, signedMap, x + 1, y, count, k);moveOne(m, n, signedMap, x, y - 1, count, k);moveOne(m, n, signedMap, x, y + 1, count, k);}//计算数字的数位之和int getSum(int number){int sum = 0;while(number != 0){sum += number % 10;number = int(number / 10);}return sum;}

个人博客

如果觉得《深度优先搜索（解题剑指Offer12 13）》对你有帮助，请点赞、收藏，并留下你的观点哦！