题目链接：/questionTerminal/6e5207314b5241fb83f2329e89fdecc8
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
第一次编辑代码：
public class Solution {boolean[] visited = null;int sum = 0;public int movingCount(int threshold, int rows, int cols){visited = new boolean[rows*cols];move(threshold,rows,cols,0,0);return sum;}public void move(int threshold, int rows, int cols,int i,int j){if(!visited[i*cols+j]){visited[i*cols+j] = true;sum++;}if(i>0 && isLegal(threshold,i-1,j))move(threshold,rows,cols,i-1,j);if(i<rows-1 && isLegal(threshold,i+1,j))move(threshold,rows,cols,i+1,j);if(j>0 && isLegal(threshold,i,j-1))move(threshold,rows,cols,i,j-1);if(j<cols-1 && isLegal(threshold,i,j+1))move(threshold,rows,cols,i,j+1);}public boolean isLegal(int threshold,int i,int j){int bit = 0;while(i>0){bit += i%10;i /= 10;}while(j>0){bit += j%10;j /= 10;}if(bit > threshold){return false;}else{return true;}}}
提交结果
请检查是否存在数组越界等非法访问情况
反思
唯一的数组是visited，且范围应该没有出现越界情况。
为什么换种方法写就能对？
第二次编辑代码：
public class Solution {boolean[] visited = null;int sum = 0;public int movingCount(int threshold, int rows, int cols){visited = new boolean[rows*cols];return move(threshold,rows,cols,0,0);}public int move(int threshold, int rows, int cols,int i,int j){if(i<0 || i>rows-1 || j<0 || j>cols-1)return 0;if(visited[i*cols+j] || !isLegal(threshold,i,j))return 0;visited[i*cols+j] = true;return 1+move(threshold,rows,cols,i-1,j)+move(threshold,rows,cols,i+1,j)+move(threshold,rows,cols,i,j-1)+move(threshold,rows,cols,i,j+1);}public boolean isLegal(int threshold,int i,int j){int bit = 0;while(i>0){bit += i%10;i /= 10;}while(j>0){bit += j%10;j /= 10;}if(bit > threshold){return false;}else{return true;}}}
反思
今天在力扣上刷到一样的题，用牛客网提交的代码无法通过，看了评论换了dfs的思路求解，更加简洁。
第三次编辑代码：
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 m, int n, int k, boolean[][] visited){if(i < 0 || i > m - 1 || j < 0 || j > n - 1 || (i/10 + i%10 + j/10 + j%10) > k || visited[i][j])return 0;visited[i][j] = true;return 1 + dfs(i - 1, j, m, n, k, visited) + dfs(i + 1, j, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);}}
