地上有一个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。
请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1 输出：3
题解：
可以使用深度优先或者广度优先算法
1.深度优先搜索
可以理解为暴力法模拟机器人在矩阵中的所有路径。
DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为 可行性剪枝 。
算法解析：
递归参数：
当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
终止条件：
- ① 行列索引越界
- ② 数位和超出目标值 k
- ③ 当前元素已访问过 时，返回 0 ，代表不计入可达解。
递推工作：
标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。
public class offer13 { public static void main(String[] args) { // TODO Auto-generated method stub int m =16,n=8; int k = 4; System.out.println(movingCount(m,n,k)); } public static int movingCount(int m, int n,int k){ boolean[][] visited = new boolean[m][n]; int ans = dfs(0,0,m,n,k,visited); return ans; } //深度优先实现 public static int dfs(int i,int j,int m,int n,int k,boolean[][] visited){ if(i<0||i>=m||j<0||j>=n||bitSum(i)+bitSum(j)>k||visited[i][j]==true){//i,j索引超出边界或者数位之和大于k,或者已经访问过了，则返回0，代表不计入可达解 return 0; } visited[i][j] = true; return 1 + dfs(i-1,j,m,n,k,visited) + dfs(i+1,j,m,n,k,visited) + dfs(i,j-1,m,n,k,visited) + dfs(i,j+1,m,n,k,visited) ; } //数位之和 public static int bitSum(int i){ int sum = 0; do{ sum+=i%10; i = i/10; }while(i!=0); return sum; } }
2.广度优先搜索
BFS/DFS ： 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现： 通常利用队列实现广度优先遍历。
算法解析：
初始化： 将机器人初始点 (0, 0) 加入队列 queue ；
迭代终止条件： queue 为空。代表已遍历完所有可达解。
迭代工作：
单元格出队： 将队首单元格的 索引 弹出，作为当前搜索单元格。
判断是否跳过：
① 行列索引越界
② 数位和超出目标值 k
③ 当前元素已访问过 时，执行 continue 。
标记当前单元格 ：将单元格索引 (i, j) 存入 Set visited 中，代表此单元格 已被访问过 。
单元格入队： 将当前元素的 下方、右方 单元格的 索引加入 queue 。
返回值： Set visited 的长度 len(visited) ，即可达解的数量。
public static int bfs(int m,int n,int k){ boolean[][] visited = new boolean[m][n]; int res = 0; Queue<int[]> queue = new LinkedList<int[]>(); queue.add(new int[]{0,0}); while(queue.size()>0){ int[] x = queue.poll(); int i = x[0],j = x[1]; if(i>=m||j>=n||bitSum(i)+bitSum(j)>k||visited[i][j]==true){ continue; } visited[i][j] = true; res++; queue.add(new int[]{i+1,j}); queue.add(new int[]{i,j+1}); } return res; }
参考题解