「剑指Offer」Day14：搜索与回溯算法（中等）
剑指 Offer 12. 矩阵中的路径
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
题目链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
题目链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
思路
深度优先遍历（DFS）+剪枝
- DFS：从当前矩阵元素的上下左右四个方向进行递归遍历
-
剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。
实现代码
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray(); //转换为字符数组方便处理
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(dfs(board, words, i, j, 0)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, char[] words, int i, int j, int k){ //深度优先遍历
//判断索引是否越界
if(i >= board.length || i < 0 || j >= board[0].length || j < 0){
return false;
}
//判断当前矩阵元素与目标字符是否相同
if(board[i][j] != words[k]){
return false;
}
//若遍历到单词的最后一个元素，就说明包含，返回true
if(k == words.length - 1){
return true;
}
//将遍历过的元素置为空字符，与目标字符判断返回false
board[i][j] = ' ';
//朝当前元素的 上、下、左、右 四个方向继续递归遍历
boolean res = dfs(board, words, i+1, j, k+1) || dfs(board, words, i-1, j, k+1) ||
dfs(board, words, i, j+1, k+1) || dfs(board, words, i, j-1, k+1);
//还原当前矩阵元素
board[i][j] = words[k];
return res;
}
}
剑指 Offer 13. 机器人的运动范围
题目描述
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
输入：m = 2, n = 3, k = 1 输出：3
思路
广度优先遍历（BFS），隐藏优化：搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索；用数组来记录各方向的坐标，而不用新建对象
实现代码
class Solution {
public int movingCount(int m, int n, int k) {
if (k == 0) {
return 1;
}
Queue<int[]> queue = new LinkedList<int[]>();
//可将搜索方向缩减为向右和向下
int[] dx = {0, 1};
int[] dy = {1, 0};
boolean[][] vis = new boolean[m][n]; //标记遍历过的位置
queue.offer(new int[]{0, 0}); //用数组记录x,y坐标
vis[0][0] = true;
int ans = 1;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int i = 0; i < 2; ++i) { //取出当前坐标，分别向右和向下移动，判断是否可达
int tx = dx[i] + x;
int ty = dy[i] + y;
if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
continue;
}
queue.offer(new int[]{tx, ty}); //可达的坐标继续入队
vis[tx][ty] = true; //遍历过的位置标记为true
ans++; //累加到达的格子数
}
}
return ans;
}
private int get(int x) { //计算数位之和
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
return res;
}
}
查看31道真题和解析