package othercode.Array;

/**

* 题目描述：

* 地上有一个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。

* 请问该机器人能够到达多少个格子？

* <p>

* 思路：使用BFS，根据可达解的结构和连通性，易推出机器人可 仅通过向右和向下移动，访问所有可达解 。

* 递归参数： 当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。

* 终止条件： 当 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时，返回 00 ，代表不计入可达解。

* 递推工作：

* 标记当前单元格 ：将索引 (i, j) 存入 visited 中，代表此单元格已被访问过。

* 搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。

* 回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

*/

public class movingCount {

boolean[][] visited;

public int movingCountSolution(int m, int n, int k) {

this.visited = new boolean[m][n];

return dfs(this.visited, m, n, 0, 0, k);

}

int dfs(boolean[][] visited, int m, int n, int i, int j, int k) {

if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]

|| (bitSum(i) + bitSum(j)) > k) {

return 0;

}

visited[i][j] = true;

return 1 + dfs(visited, m, n, i + 1, j, k) + dfs(visited, m, n, i, j + 1, k);

}

int bitSum(int i) {

int res = 0;

while (i > 0) {

res += i % 10;

i = i / 10;

}

return res;

}

}