class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
int res = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {0, 0, 0, 0});
while (queue.size() > 0) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1], sx = cell[2], sy = cell[3];
if (x >= m || y >= n || sx + sy > k || visited[x][y]) {
continue;
}
visited[x][y] = true;
res ++;
//往右走，数位之和使用增量存储计算
queue.add(new int[]{x, y + 1, sx, (sy + 1 % 10 == 0 ? sy - 8 : sy + 1)});
//往下走
queue.add(new int[]{x + 1, y, (sx + 1 % 10 == 0 ? sx - 8 : sx + 1), sy});
}
return res;
}
}
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
return dfs(visited, m, n, k, 0, 0);
}
int dfs(boolean[][] visited, int m, int n, int k, int i, int j) {
if (i >= m || j >= n || visited[i][j] || (sum(i) + sum(j)) > k) {
return 0;// 不满足条件的情况
}
visited[i][j] = true;
// 向右或者向下
return dfs(visited, m, n, k, i + 1, j) + dfs(visited, m, n, k, i, j + 1) + 1;
}
// 计算数位和
int sum(int i) {
int res = 0;
while (i != 0) {
res += i % 10;
i /= 10;
}
return res;
}
}
class Solution {
private int m;
private int n;
private int k;
private boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m;
this.n = n;
this.k =k;
visited = new boolean[m][n];
return dfs(0,0);
}
public int dfs(int row, int col) {
if (row >= m || col >= n || visited[row][col] || k < sum (row, col)) {
return 0;
}
visited[row][col] = true;
return 1 + dfs(row + 1, col) + dfs(row, col + 1);
}
public int sum(int m, int n) {
int res = 0;
while (m != 0) {
res += m % 10;
m /= 10;
}
while (n != 0) {
res += n % 10;
n /= 10;
}
return res;
}
}
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
return dfs(0, 0, m, n, k, visited);
}
public int dfs(int i, int j, int rows, int cols, int threshold, boolean[][] visited) {
if (i >= rows || j >= cols || threshold < sum(i, j) || visited[i][j])
return 0;
visited[i][j] = true;
//沿着当前格子的右边和下边继续访问
return 1 + dfs(i + 1, j, rows, cols, threshold, visited) +
dfs(i, j + 1, rows, cols, threshold, visited);
}
public int sum(int i, int j){
int res = 0;
while(i != 0){
res += i % 10;
i /= 10;
}
while(j != 0){
res += j % 10;
j /= 10;
}
return res;
}
}
2、bfs，先把最近的都访问一遍，访问完之后才开始访问第二近的…，使用队列，先进先出
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
int res = 0;
Queue<int[]> queue = new LinkedList<int[]>();
// 从左上角坐标[0,0]点开始访问
queue.add(new int[]{0,0});
while(!queue.isEmpty()){
int[] x = queue.poll();
int i=x[0], j=x[1];
if (i >= m || j >= n || k < sum(i, j) || visited[i][j])
continue;
visited[i][j] = true;
res++;
// 把当前格子右边格子的坐标加入到队列中
queue.add(new int[]{i + 1, j});
// 把当前格子下边格子的坐标加入到队列中
queue.add(new int[]{i, j + 1});
}
return res;
}
public int sum(int i, int j){
int res = 0;
while(i != 0){
res += i % 10;
i /= 10;
}
while(j != 0){
res += j % 10;
j /= 10;
}
return res;
}
}
// dfs思想：
class Solution {
public:
void dfs(int m,int n,int k,int& count,int i,int j,vector<vector<bool>> &vsitied)
{
if((sum(i)+sum(j)>k)||i<0||i>=m||j<0||j>=n) return;
if(vsitied[i][j]) return;
vsitied[i][j]=true;
dfs(m,n,k,count,i+1,j,vsitied);
dfs(m,n,k,count,i,j+1,vsitied);
count++;
//vsitied[i][j]=false;
}
int movingCount(int m, int n, int k) {
int count = 0;
vector<vector<bool>> vsitied(m,vector<bool>(n,false));
dfs(m,n,k,count,0,0,vsitied);
return count;
}
int sum(int x) {
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
return res;
}
};
shuaidi
共以下 5 个回答
深度优先遍历，时间复杂度和空间复杂度均为O(mn)
1、dfs，沿着一个方向一直往下走
2、bfs，先把最近的都访问一遍，访问完之后才开始访问第二近的…，使用队列，先进先出