class Solution {
class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public int movingCount(int threshold, int rows, int cols)
{
if(rows == 0 && cols == 0 ) {
return 0;
}
boolean[][] flags = new boolean[rows][cols];
Stack<Node> stack = new Stack();
int count = 0;
int[] a = new int[]{-1,0,1,0};
int[] b = new int[]{0,-1,0,1};
Node node = new Node(0,0);
flags[0][0] = true;
count++;
stack.push(node);
while(!stack.isEmpty()) {
Node n = stack.pop();
for(int k = 0; k < a.length; k++) {
int x = n.x + b[k];
int y = n.y + a[k];
if(x >= 0 && x <rows && y >= 0 && y < cols && !flags[x][y] && count(x,y,threshold)) {
flags[x][y] = true;
count++;
stack.push(new Node(x,y));
}
}
}
return count;
}
public boolean count(int i, int j, int threshold) {
int count = 0;
while(i != 0) {
count += (i % 10);
i = i / 10;
}
while(j != 0) {
count += (j % 10);
j = j / 10;
}
return count > threshold ? false : true;
}
}
1.想要做到走过的路再回退回来,可以想到栈