题目：
题解：
解题所需前提：
1、深度优先遍历
解题思路：本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。
- 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
- 剪枝： 在搜索中，遇到
这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。
复杂度分析：
设矩阵行列数分别为 M, N 。
时间复杂度 O(MN) ： 最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN) 。
空间复杂度 O(MN) ： 最差情况下，visited 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。代码：
普通版（未使用位数和规则）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// 深度优先遍历，普通
class Solution {
public int movingCount(int m, int n, int k) {
// 判断是否重复
boolean[][] visited = new boolean[m][n];
return dfs(0,0,m,n,k,visited);
}
private int dfs(int a, int b, int m, int n, int k, boolean[][] visited) {
if (a >= 0 && a < m && b >= 0 && b < n
&& (a % 10 + a / 10 + a / 100 + b % 10 + b / 10 + b / 100) <= k
&& visited[a][b] == false) {
visited[a][b] = true;
// 1是(0,0)位置，只需递归他右面和下面的即可
return 1 + dfs(a + 1, b, m, n, k, visited) + dfs(a, b + 1, m, n, k, visited);
}else return 0;
}
}复杂版（使用位数和规则）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// 深度优先遍历，复杂（找到位数和的规律，不需要每次计算，直接递归即可），第一种的优化
class Solution2 {
int m, n, k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m; this.n = n; this.k = k;
this.visited = new boolean[m][n];
return dfs(0, 0, 0, 0);
}
// 当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj
public int dfs(int i, int j, int si, int sj) {
if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
visited[i][j] = true;
return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
}
}
2、广度优先遍历
解题思路：
复杂度分析：
设矩阵行列数分别为 M, N 。
时间复杂度 O(MN) ： 最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN) 。
空间复杂度 O(MN) ： 最差情况下，visited 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// 广度优先遍历
class Solution3 {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
int count = 0;
LinkedList<int[]> queue = new LinkedList<>();
queue.add(new int[] {0,0,0,0});
while (queue.size() > 0) {
int[] poll = queue.poll();
int i = poll[0],j = poll[1],si = poll[2],sj = poll[3];
if (i >= m || j >= n || si + sj > k || visited[i][j]) continue;
visited[i][j] = true;
count++;
queue.add(new int[] {i + 1,j,(i + 1) % 10 != 0 ? si + 1 : si - 8, sj});
queue.add(new int[] {i ,j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8});
}
return count;
}
}