BFS

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/22/]

地上有一个m 行和n列的方格，横纵坐标范围分别是 0∼m−1 和0∼n−1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 kk 的格子。

请问该机器人能够达到多少个格子？

样例1

1
2
3
输入：k=7, m=4, n=5

输出：20

样例2

1
2
3
4
5
6
输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

注意:

  1. 0<=m<=50
  2. 0<=n<=50
  3. 0<=k<=100

算法描述

简单的BFS，当数据量太大的话DFS可能会造成栈溢出的错误，所以这种题适合用BFS去解决

明显的思路，就是从左上角开始一直扩展，以栈为载体，每次有四种扩张的方式，满足题目要求的数据就压入栈中，直至栈为空返回计数器ans;

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    
    int getSingalSum(int num){
        int s=0;
        while(num)s+=num%10,num=num/10;
        return s;
    }
    
    int getSum(pair<int,int> p){
        return getSingalSum(p.first)+getSingalSum(p.second);
    }
    
    
    int movingCount(int threshold, int rows, int cols)
    {
        int ans=0;
        if(!rows||!cols)return ans;
        vector<vector<bool>> b(rows,vector<bool>(cols,false));
        queue<pair<int,int>> que;
        que.push({0,0});
        while(!que.empty()){
            pair<int,int> p=que.front();
            que.pop();
            int dx[]={0,-1,0,1},dy[]={1,0,-1,0};
            
            int sum = getSum(p);
            if(sum>threshold||b[p.first][p.second])continue;
            ans++;
            b[p.first][p.second]=true;
            
            for(int i=0;i<4;i++){
                int x = p.first+dx[i],y = p.second+dy[i];
                if(x>=0&&x<rows&&y>=0&&y<cols){
                    que.push({x,y});
                }
            }
        }
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    
    public int getSingalSum(int num){
        int s=0;
        while(num!=0){s+=num%10;num=num/10;}
        return s;
    }
    
    public int getSum(Integer[] sum){
        return getSingalSum(sum[0])+getSingalSum(sum[1]);
    }
    
    public int movingCount(int threshold, int rows, int cols)
    {
        int ans=0;
        if(rows==0||cols==0)return ans;
        boolean[][] b = new boolean[rows][cols];
        Queue<Integer[]> que = new LinkedList<>();
    
        que.offer(new Integer[]{0,0});
        while(que.size()!=0){
            Integer[] t = que.poll();
            int sum = getSum(t);
            
            int dx[]={0,-1,0,1},dy[]={1,0,-1,0};
            
            if(sum>threshold||b[t[0]][t[1]])continue;
            ans++;
            b[t[0]][t[1]]=true;
            
            for(int i=0;i<4;i++){
                int x= t[0]+dx[i],y = t[1]+dy[i];
                if(x>=0&&x<rows&&y>=0&&y<cols){
                    que.offer(new Integer[]{x,y});
                }
            }
            
        }
        return ans;
    }
}