[剑指offer][JAVA][面试题第13题][机器人的运动][DFS][BFS]

【问题描述】 [中等]

地上有一个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：输入：m = 3, n = 1, k = 0输出：1提示：1 <= n,m <= 1000 <= k <= 20

【解答思路】

题目分析:题意是一个人从（0，0）开始向走，可以走四个方向，它下一个走到的地方的坐标数位之和不超过k，问这个人最多可以走多少个格子

1. DFS

从起点开始用深搜的方式遍历矩阵 只向下或者向右控制深搜边界的同时判断当前访问的位置数位和是否小于等于k需要一个标记数组记录每个位置的访问情况，防止重复计算

时间复杂度：O(N^2) 空间复杂度：O(N)

class Solution {int m,n,k;public int movingCount(int m, int n, int k) {this.m=m;this.n=n;this.k=k;//标记访问过的位置boolean[][] visited=new boolean[m][n];return dfs(0,0,0,visited);}/*** 深搜* @param i 横坐标* @param j 纵坐标* @param sum 坐标数位和* @param visited 标记数组* @return*/private int dfs(int i, int j, int sum, boolean[][] visited) {//如果 坐标越界 或者 数位和大于k 或者 已经访问过，则停止当前方向的深搜if (i==m||j==n||sum>k||visited[i][j])return 0;//标记为已访问visited[i][j]=true;//向下或者向右深搜return 1+dfs(i+1,j,sums(i+1,j),visited)+dfs(i,j+1,sums(i,j+1),visited);}//计算数位和public int sums(int x,int y){int ans=0;while (x != 0) {ans+=x%10;x/=10;}while (y != 0) {ans+=y%10;y/=10;}return ans;}}

2. BFS(队列)

从起点开始用深搜的方式遍历矩阵 只向下或者向右控制深搜边界的同时判断当前访问的位置数位和是否小于等于k需要一个标记数组记录每个位置的访问情况，防止重复计算

时间复杂度：O(N) 空间复杂度：O(N)

//时间复杂度：O(mn)public int movingCount(int m, int n, int k) {//队列保存坐标Queue<int[]> queue=new ArrayDeque<>();//标记数组boolean[][] visited=new boolean[m][n];//广搜queue.add(new int[]{0,0});int count=0;visited[0][0]=true;while (!queue.isEmpty()) {int[] poll = queue.poll();count++;//向下、向右寻找符合要求的位置入队并标记访问状态//不越界 并且 数位和小于等于k 并且 未访问过if (poll[0] + 1 < m&& sums(poll[0] + 1, poll[1]) <= k&&!visited[poll[0]+1][poll[1]]){queue.add(new int[]{poll[0]+1,poll[1]});visited[poll[0]+1][poll[1]]=true;}if (poll[1] + 1 < n&& sums(poll[0], poll[1] + 1) <= k&&!visited[poll[0]][poll[1] + 1]){queue.add(new int[]{poll[0],poll[1]+1});visited[poll[0]][poll[1]+1]=true;}}return count;}//计算数位和public int sums(int x,int y){int ans=0;while (x != 0) {ans+=x%10;x/=10;}while (y != 0) {ans+=y%10;y/=10;}return ans;}

【总结】

1. BFS

确定递归参数终止条件标记数组记录每个位置的访问情况计数在递归回溯中 （同广度）

2. DFS

队列 （出队后搜索符合条件入队）终止条件标记数组记录每个位置的访问情况计数在所有相同深度出完队列之后

3. BFS DFS 分步思考 效果佳

4.100以内数之和