地上有一个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
示例 2:
输入:m = 3, n = 1, k = 0
输出:1
原题链接文章来源地址https://www.toymoban.com/news/detail-672684.html
- 我的思路:从左上角 [0,0] 开始 dfs,如果行列坐标的数位之和大于 k 就返回 0,如果来过了这个点也返回 0,如果超出边界了也返回 0,否则就算是一个能够到达的格子,返回 1+dfs(往右走)+dfs(往下走)。因为是从左上角开始,所以往右和往下足以遍历每个格子。
-
int M,N,K; Set<Integer> set = new HashSet<>(); public int movingCount(int m, int n, int k) { M=m; N=n; K=k; return dfs(0,0); } public int dfs(int x,int y){ // 超出边界 if(x>=M || y>=N)return 0; // 不符题意 if(getNum(x,y)>K)return 0; // 已计算过 if(set.contains(x*N+y))return 0; set.add(x*N+y); int ans = dfs(x+1,y)+dfs(x,y+1)+1; return ans; } // 获取格子行列数位和 public int getNum(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; }
- 他人题解:获取格子行列数位和这部分可以优化,以下用 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%10==0?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.m=m;this.n=n;this.k=k; this.see = new boolean[m][n]; return dfs(0,0,0,0); } public int dfs(int x,int y,int sx,int sy){ if(x>=m || y>=n || sx+sy>k || see[x][y])return 0; see[x][y]=true; int newSx = (x+1)%10==0?sx-8:sx+1; int newSy = (y+1)%10==0?sy-8:sy+1; int ans = dfs(x+1,y,newSx,sy)+dfs(x,y+1,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; Queue<int[]> queue= new LinkedList<int[]>(); // 熟悉的 dfs 入参,坐标以及坐标对应的 sum queue.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 0 if(i >= m || j >= n || k < si + sj || visited[i][j]) continue; visited[i][j] = true; // 以下三行相当于 return dfs(下)+dfs(右)+1 res ++; 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; }
文章来源:https://www.toymoban.com/news/detail-672684.html
到了这里,关于从零学算法 (剑指 Offer 13)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!