剑指Offer 13:机器人的运动范围 【中等】”
题目描述
此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。
我们使用==递归==的方式进行完成。首先我们自己来初始化一个boolen[][]
矩阵,用来标记每一个方格是否可达。如果当前方格(i,j)
可达,我们继续向下和向右遍历,如果当前方格(i,j)
不可达,那么我们则不再需要继续向后递归。
当我们完成整个方格的标记之后,我们遍历存放可达的boolean
矩阵,然后进行统计可达的个数就好了~
代码实现:
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] flag = new boolean[m][n];//记录访问了哪些格子
extend(flag , 0 , 0 , m , n , k);
int res = 0;
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(!flag[i][j]) continue;//如果当前的格子已经遍历过了,则不再进行遍历了
res++;
}
}
return res;
}
private void extend (boolean[][] flag , int row , int col , int m , int n , int k){
//判断当前格子是否已经超出范围并且确保没有被访问过
if(row < 0 || row >= m || col < 0 || col >= n || flag[row][col]) return;
int sum = 0 ;
int i = row , j = col ;
while(row > 0 || col > 0){
sum += row%10 + col%10;
row /= 10;
col /= 10;
}
if(sum > k) return; //判断是否可达
flag[i][j] = true;
//我们规定机器人都是从左上角开始移动的,所以我们只需要让机器人向右或者向下即可
extend(flag , i+1 , j , m , n , k);//向下
extend(flag , i , j+1 , m , n , k);//向右
}
}
此题的解题思路是比较明显的,就是递归思想,在很多题解里面所说的DFS
其实本质上也是一种递归的表现形式,首先弄清楚何时递归,何时不可递归,以及每次递归时我们需要的处理即可。大致可以从这道题目中略见一二。