AcWing 24. 机器人的运动范围（C++）- BFS+有价值

红太狼 2022-09-14 15:15 24阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/22/][https_www.acwing.com_problem_content_description_22]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
    public:
        int movingCount(int threshold, int rows, int cols)
        {
        
            if(rows==0&&cols==0) return 0;
            if(threshold==0) return 1;
            int result=0;
            
            //从(0,0)开始的坐标，从时钟9开始顺时针旋转；bfs
            int dx[4]={
        -1,0,1,0};
            int dy[4]={
        0,1,0,-1};
            vector<vector<bool>> visited(rows,vector<bool>(cols,false));//用来存放访问过的节点
             
            queue<pair<int,int>> que;//存放每次经过的坐标
            que.push({
        0,0});       
            
            while(!que.empty()){
        
                auto tmp=que.front();//或者auto [x,y]=que.front();
                que.pop();
                
                if(visited[tmp.first][tmp.second]==true||get(tmp.first)+get(tmp.second)>threshold) continue;//不满足的直接continue
                //满足的情况
                result++;
                visited[tmp.first][tmp.second]=true;
                
                for(int i=0;i<4;++i){
        
                    int x=dx[i]+tmp.first;
                    int y=dy[i]+tmp.second;
                    
                    if(x>=0&&x<rows&&y>=0&&y<cols) que.push({
        x,y});//把所有可能的节点都放入que中
                }
            }
            
            return result;
            
        }
        
        //求每个数字的各位数字之和
        int get(int num){
        
            int sum=0;
            
            while(num!=0){
        
                sum+=num%10;
                num=num/10;
            }
            
            return sum;
        }
    };

[https_www.acwing.com_problem_content_description_22]: https://www.acwing.com/problem/content/description/22/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c3540b48ff654da6ac1de5d324ed2089.png