设计网站建设合同书6,湛江制作网站企业,产业互联网平台,医院网站模板下载文章目录题目描述思路 代码二刷题目描述
注意点#xff1a;满足数位和大于 k 的格子#xff0c;不一定可以从 [0, 0] 走到#xff0c;因此实际上不满足条件
思路 代码
考虑到可达性问题#xff0c;决定用 dfs 来一个个走#xff0c;不能走 or 走过了就 re…
文章目录题目描述思路 代码二刷题目描述
注意点满足数位和大于 k 的格子不一定可以从 [0, 0] 走到因此实际上不满足条件
思路 代码
考虑到可达性问题决定用 dfs 来一个个走不能走 or 走过了就 return用辅助矩阵来判断是否走过 visited[ ][ ]时空复杂度 O(n2n^2n2)、O(n2n^2n2)
class Solution {int ans 0;boolean[][] visited;public int movingCount(int m, int n, int k) {visited new boolean[m][n];dfs(m, n, k, 0, 0);return ans;}// 行走void dfs(int m, int n, int k, int x, int y){// 来过了就不再来咯越界也结束咯if(x m || y n || visited[x][y]){return;}// 可以走的话继续往下走if(sum(x) sum(y) k){ans;visited[x][y] true;dfs(m, n, k, x 1, y);dfs(m, n, k, x, y 1);} }// 数位和判断int sum(int x){int sum 0;while(x 0){sum x % 10;x / 10;}return sum;}
}二刷
其实 i j 是有范围限制的否则需要像上面的代码那样写一个数位和判断。注意从[0, 0]出发可能有些满足 k 条件的格子其实并不能走到
class Solution {boolean[][] graph;int counts 0;public int movingCount(int m, int n, int k) {graph new boolean[m][n];infect(0, 0, m, n, k);return counts;}void infect(int i, int j, int m, int n, int k) {if(i 0 || i m || j 0 || j n || (i % 10 i / 10 j % 10 j / 10) k || graph[i][j]) {return;}graph[i][j] true;counts;infect(i 1, j, m, n, k);infect(i, j 1, m, n, k);}
}
