郑州手机网站制作公司哪家好,企业网站制作套餐,不用写代码做网站,长沙网页制作公司地上有一个m行n列的方格#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动#xff0c;它每次可以向左、右、上、下移动一格#xff08;不能移动到方格外#xff09;#xff0c;也不能进入行坐标和列坐标的数位之和大于k的格子。例如从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动它每次可以向左、右、上、下移动一格不能移动到方格外也不能进入行坐标和列坐标的数位之和大于k的格子。例如当k为18时机器人能够进入方格 [35, 37] 因为353718。但它不能进入方格 [35, 38]因为353819。请问该机器人能够到达多少个格子 示例 1 输入m 2, n 3, k 1 输出3 示例 2 输入m 3, n 1, k 0 输出1 原题链接 我的思路从左上角 [0,0] 开始 dfs如果行列坐标的数位之和大于 k 就返回 0如果来过了这个点也返回 0如果超出边界了也返回 0否则就算是一个能够到达的格子返回 1dfs(往右走)dfs(往下走)。因为是从左上角开始所以往右和往下足以遍历每个格子。 int M,N,K;SetInteger set new HashSet();public int movingCount(int m, int n, int k) {Mm;Nn;Kk;return dfs(0,0);}public int dfs(int x,int y){// 超出边界if(xM || yN)return 0;// 不符题意if(getNum(x,y)K)return 0;// 已计算过if(set.contains(x*Ny))return 0;set.add(x*Ny);int ans dfs(x1,y)dfs(x,y1)1;return ans;}// 获取格子行列数位和public int getNum(int x,int y){int ans 0;while(x0){ansx%10;x/10;}while(y0){ansy%10;y/10;}return ans;}他人题解获取格子行列数位和这部分可以优化以下用 sum 代替一个数的数位和 。一个数在递增的时候只要没满十规律都是 sum(x)sum(x-1)1比如 16 和 17 和 18 的 sum 就是 7-8-9。如果满十进一了就相当于把原本的 9 变成了 0之前的一位加了 1算下来就是减少了 8所以此时 sum(x) sum(x-1)-8总结一下就是 sum(x) x%100?s(x-1)-8:sum(x-1)1。也就是说一个坐标的行列在变化时他的数位和就能根据这个规律来计算所以在 dfs 的入参中加入坐标 [i,j] 对应的 sum(i) 和 sum(j)就能递推得到一个坐标的数位和。 int m,n,k;// 用数组判断是否来过某个点更快boolean[][] see;public int movingCount(int m, int n, int k) {this.mm;this.nn;this.kk;this.see new boolean[m][n];return dfs(0,0,0,0);}public int dfs(int x,int y,int sx,int sy){if(xm || yn || sxsyk || see[x][y])return 0;see[x][y]true;int newSx (x1)%100?sx-8:sx1;int newSy (y1)%100?sy-8:sy1;int ans dfs(x1,y,newSx,sy)dfs(x,y1,sx,newSy)1;return ans;}他人题解2既然是遍历每个格子那其实 bfs 也行原理都一样就不赘述了 public int movingCount(int m, int n, int k) {boolean[][] visited new boolean[m][n];int res 0;Queueint[] queue new LinkedListint[]();// 熟悉的 dfs 入参坐标以及坐标对应的 sumqueue.add(new int[] { 0, 0, 0, 0 });while(queue.size() 0) {int[] x queue.poll();int i x[0], j x[1], si x[2], sj x[3];// 相当于 dfs 的 return 0if(i m || j n || k si sj || visited[i][j]) continue;visited[i][j] true;// 以下三行相当于 return dfs(下)dfs(右)1res ;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 res;}
