[//]: # 机器人的运动范围 c++ dfs bfs 简介

题目描述

很久没做过题了，下周考蓝桥杯，临阵复习下。感觉这题很适合拿来写dfs 和 bfs
经典的格子问题，题目本身注意一个坑：数位之和，不是和。这个wa了一下。
bfs也踩了一个小坑，坐标加入队列可以进行状态更新。

DFS

C++ 代码

class Solution {
public:
int k,m,n,cnt = 0;
bool vis[55][55];
int xm[4]={1,0,-1,0},ym[4]={0,1,0,-1};

    int movingCount(int threshold, int rows, int cols)
    {
        k = threshold,m = rows , n = cols;
        dfs(0,0);
    for(int i = 0;i < m;i++){
        for(int j = 0 ; j < n; j++){
            if(vis[i][j] )cnt++;
        }
    }
    return cnt;
    }
    bool canMove(int x,int y){ //可以返回1 
    if(x%10 + x/10 + y/10 + y%10 > k) return 0;
    if(x >= m || x < 0)return 0;
    if(y >=n || y <0) return 0;
    if(vis[x][y])return 0;
    return 1;
}
void dfs(int x,int y){
    vis[x][y] = 1;
    for(int i = 0;i < 4;i ++) 
        if( canMove(x+xm[i],y + ym[i]) ) {
            vis[x+xm[i]][y + ym[i]] = true;
            dfs(x+xm[i],y + ym[i]);
        }
    //不需要恢复现场 
}
};

算法2

BFS

C++ 代码

class Solution {
public:
    queue<pair<int ,int>> q;
    int k,m,n,dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
    bool vis[55][55];
    bool canmove(pair<int,int> p){
        int x = p.first, y = p.second;
        if(x%10 + x/10 + y/10 + y%10 > k) return 0;
        if(x >= m || x < 0)return 0;
        if(y >=n || y <0) return 0;
        if(vis[x][y])return 0;
        return 1;
    }
    void bfs(){
        auto p = q.front();
        q.pop();
        int x = p.first,y = p.second;
        vis[x][y]=1;
        for(int i=0;i<4;i++){
            if(canmove({x +dx[i],y+dy[i]})) 
            {
                vis[x +dx[i]][y+dy[i]]=1;
                q.push({x +dx[i],y+dy[i]});
            }
        }
    }
    int movingCount(int threshold, int rows, int cols)
    {
        k = threshold,m = rows,n = cols;
        q.push({0,0});
        while(q.size()) bfs();
        int cnt = 0;
        for(int i = 0;i < m;i++){
        for(int j = 0 ; j < n; j++){
            if(vis[i][j] ){
                cnt++;
            }
        }
    }
        return cnt;
    }
};