题目的链接在这里：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
目录
题目大意
地上有一个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。请问该机器人能够到达多少个格子？一、示意图
二、解题思路
递归 DFS BFS
递归
代码如下：
class Solution {
boolean [][] visited;
//然后是记录格子数的吧
// static int step;
public int movingCount(int m, int n, int k) {
//直接初始化
visited=new boolean[m][n];
return dfs(0,0,visited,k,m,n);
}
//其实是使用了递归
private int dfs(int i, int j, boolean[][] visited, int k, int m, int n) {
//然后这里开始判断
if(i<0||i>=m||j<0||j>=n||(getNum(i)+getNum(j)>k)||visited[i][j]){
//满足这个条件的
return 0;
}
//不然的话 就判断他的四周 并说明这个点本身就是可以的 还需要再加一
visited[i][j]=true;
return dfs(i+1,j,visited,k,m,n)+dfs(i-1,j,visited,k,m,n)+dfs(i,j+1,visited,k,m,n)+dfs(i,j-1,visited,k,m,n)+1;
}
private int getNum(int i) {
//要么就是写一个方法来求 i和j的数位合
/* if(i<10){
return i;
}*/
if(i>=10&&i<=99){
int temp1=i/10;
int temp2=i%10;
return temp1+temp2;
}
return i;
}
}
DFS
代码如下：
class Solution {
//坑定有个矩阵用来判断这个位置有没有走过
boolean [][] visited;
//然后是DFS
int x[]={0,0,-1,1};
int y[]={1,-1,0,0};
int count;
public int movingCount(int m, int n, int k) {
//直接初始化
visited=new boolean[m][n];
count=0;
//然后遍历第一个 并开始积累
dfs(0,0,m,n,k,visited);
return count;
}
private void dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
//先进行判断
if(i>=m||j>=n)
return;
//然后判断是不是满足
if(i>=0&&i<m&&j>=0&&j<n&&!visited[i][j]&&(getNum(i)+getNum(j)<=k)){
//说明这个点是满足的
count++;
visited[i][j]=true;
//然后遍历他的其他的 这边就不能用for循环
for(int l=0;l<4;l++){
dfs(i+x[l],j+y[l],m,n,k,visited);
}
}
}
private int getNum(int i) {
//要么就是写一个方法来求 i和j的数位合
/* if(i<10){
return i;
}*/
if(i>=10&&i<=99){
int temp1=i/10;
int temp2=i%10;
return temp1+temp2;
}
return i;
}
}
BFS
代码如下：
class Solution {
//坑定有个矩阵用来判断这个位置有没有走过
boolean [][] visited;
//然后是DFS
int x[]={0,0,-1,1};
int y[]={1,-1,0,0};
int count;
public int movingCount(int m, int n, int k) {
//BFS的话 就是进栈 站内应该是一个 m和n组成的吧
visited=new boolean[m][n];
Queue<List<Integer>> queue=new LinkedList<>();
List<Integer> list=new ArrayList<>();
list.add(0);
list.add(0);
//然后就开始判断他周围的
queue.add(list);
count=0;
visited[0][0]=true;
while (!queue.isEmpty()){
//取出栈顶元素
List<Integer> poll = queue.poll();
//然后取出栈顶元素中的两个值
int i=poll.get(0);
int j=poll.get(1);
// visited[i][j]=true;
//然后count++ 每次出栈都记录一下就行了
count++;
//然后判断这个点的相邻点符不符合条件
for(int l=0;l<4;l++){
int new_i=i+x[l];
int new_j=j+y[l];
//然后进行判断
if(new_i>=0&&new_i<m&&new_j>=0&&new_j<n&&!visited[new_i][new_j]&&(getNum(new_i)+getNum(new_j)<=k)){
//满足条件的话 就进队列
List<Integer> temp=new ArrayList<>();
//会导致 1 1出现两次 所有应该在这就设置为true
temp.add(new_i);
temp.add(new_j);
visited[new_i][new_j]=true;
queue.add(temp);
}
}
}
return count;
}
private int getNum(int i) {
//要么就是写一个方法来求 i和j的数位合
/* if(i<10){
return i;
}*/
if(i>=10&&i<=99){
int temp1=i/10;
int temp2=i%10;
return temp1+temp2;
}
return i;
}
}