BFS做法
时间复杂度:$O(nm)$
空间复杂度:$O(2nm)$
思路:
从第一个格子开始一步一步的合法(在区域内、未访问过、数位之和不大于$k$)的扩展节点,直到不能扩展为止
class Solution {
public static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int count(int x, int y) {
int sum = 0;
while(x > 0) {
sum += x % 10;
x /= 10;
}
while(y > 0) {
sum += y % 10;
y /= 10;
}
return sum;
}
private static boolean[][] flag = new boolean[55][55];
private static int[] dx = {0, 1, 0, -1};
private static int[] dy = {-1, 0, 1, 0};
public int movingCount(int threshold, int rows, int cols) {
if(rows < 1 || cols < 1) return 0;
int cnt = 1;
flag[0][0] = true;
Queue<Node> q = new LinkedList<>();
q.add(new Node(0, 0));
while(q.size() > 0) {
Node t = q.poll();
for(int i = 0; i < 4; ++i) {
int x = t.x + dx[i];
int y = t.y + dy[i];
if(x >= 0 && x < rows && y >= 0 && y < cols && !flag[x][y] && count(x, y) <= threshold) {
++cnt;
flag[x][y] = true;
q.add(new Node(x, y));
}
}
}
return cnt;
}
}
自己做法(暴力)
时间复杂度:$O(nm)$
空间复杂度:$O(nm)$
思路:
遍历每个格子,统计数位之和是否小于等于$k$并检查相邻格子(上下左右)是否访问过,如果相邻格子访问过的话,说明符合题目条件(每一次只能向左,右,上,下四个方向移动一格)。
class Solution {
public static int count(int x) {
int sum = 0;
while(x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
private static boolean[][] flag = new boolean[55][55];
private static int[] dx = {0, 1, 0, -1};
private static int[] dy = {-1, 0, 1, 0};
private static int rows;
private static int cols;
public boolean check(int _x, int _y) {
for(int i = 0; i < 4; ++i) {
int x = _x + dx[i];
int y = _y + dy[i];
if(x >= 0 && x < rows && y >= 0 && y < cols && flag[x][y]) {
return true;
}
}
return false;
}
public int movingCount(int threshold, int rows, int cols) {
if(rows <= 0 || cols <= 0) return 0;
this.rows = rows;
this.cols = cols;
int cnt = 1;
flag[0][0] = true;
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
int x = count(i);
int y = count(j);
if(x + y <= threshold && check(i, j)) {
++cnt;
flag[i][j] = true;
}
}
}
return cnt;
}
}