题目描述

算法1

提供一种不需要dfs，不需要队列辅助的方法，两层循环搞定
其实对于i，j步能不能走，只与两个条件有关：1）是否大于阈值 2）它左边的点或者上边的点是否可以访问
用一个二维数组vis维护地图上能被访问的格子，循环扫一遍，在当前点可以被访问的情况下，更新它四个方向能否被访问，在当前点不能被访问的情况下，直接跳过

C++ 代码

class Solution {
public:

bool check (int tl,int row, int col , int x, int y){
    if(x >=0 && x<row && y >= 0 && y < col && getnum(x)+getnum(y)<=tl){
        return true;
    }
    return false;
}
int getnum(int number){
    int sum = 0;
    while(number>0){
        sum +=(number%10);
        number/=10;
    }
    return sum;
}
int movingCount(int threshold, int rows, int cols)
{
    int vis[rows][cols];
    memset(vis,0,sizeof(vis));
    if (threshold<=0) return 1;
    vis[0][0] = 1;
    int sum=0;
    for(int i = 0;i<rows;i++)
        for(int j=0;j<cols;j++){
            if (i == 0 && j==0) continue;
            if (i-1 >=0 && vis[i-1][j]){
                if (check(threshold,rows,cols,i,j)){
                    vis[i][j] = 1;
                }
                else{
                    continue;
                }
            }
            else if (j-1 >= 0 && vis[i][j-1]){
                if (check(threshold,rows,cols,i,j)){
                    vis[i][j] = 1;
                }
                else{
                    continue;
                }
            }
            else{
                 continue;
            }
            if (check(threshold,rows,cols,i+1,j) && !vis[i+1][j]){
                vis[i+1][j] =1;
            }
            if (check(threshold,rows,cols,i,j+1) && !vis[i][j+1]){
                vis[i][j+1]=1;
            }
            if (check(threshold,rows,cols,i-1,j) && !vis[i-1][j]){
                vis[i-1][j] =1;
            }
            if (check(threshold,rows,cols,i,j-1) && !vis[i][j-1]){
                vis[i][j-1]=1;
            }
        }
    for(int i = 0;i<rows;i++)
        for(int j=0;j<cols;j++){
            if (vis[i][j]) sum+=1;
        }
    return sum;
}

};