地上有一个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
提示：
1 <= n,m <= 100
0 <= k <= 20
BFS:
class Solution {
int m;
int n;
public int movingCount(int m, int n, int k) {
this.m = m;
this.n = n;
int cnt = 0;
Queue<Node> queue = new LinkedList<>();
boolean[][] vis = new boolean[m][n];
int[][] dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
queue.add(new Node(0,0));
while(!queue.isEmpty()){
int len = queue.size();
for(int i = 0; i < len; i++){
Node node = queue.poll();
// if(inArea(node.x, newY) && !vis[node.x][newY] && (check(newX) + check(newY)) <= k){
for(int j = 0; j < 4; j++){
int newX = node.x + dir[j][0];
int newY = node.y + dir[j][1];
if(inArea(newX, newY) && !vis[newX][newY] && (check(newX) + check(newY)) <= k){
cnt++;
vis[newX][newY] = true;
queue.add(new Node(newX, newY));
}
}
}
}
return k == 0 ? 1 : cnt;
}
public boolean inArea(int x, int y){
if(x >= 0 && x < m && y >= 0 && y < n) return true;
return false;
}
public int check(int n){
int ans = 0;
while(n != 0){
ans += (n%10);
n /= 10;
}
return ans;
}
}
class Node{
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
DFS:
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] vis = new boolean[m][n];
return dfs(0, 0, m, n, k, vis);
}
public int dfs(int i, int j, int m, int n, int k, boolean[][] vis){
if(i < 0 || j < 0 || i >= m || j >= n || (i % 10 + j % 10 + i / 10 + j / 10) > k || vis[i][j]){
return 0;
}
vis[i][j] = true;
return dfs(i + 1, j, m, n, k, vis) + dfs(i, j + 1, m, n, k, vis) + dfs(i - 1, j, m, n, k, vis) + dfs(i, j - 1, m, n, k, vis) + 1;
}
}