首页 > 其他分享 >多源bfs

多源bfs

时间:2023-02-13 10:13:04浏览次数:35  
标签:cnt tx ty int bfs grid 多源 dis

输入

第一行两个整数n,m。

接下来一个N行M列的01矩阵,数字之间没有空格。

数据范围

1≤N,M≤1000

 

输出

一个N行M列的矩阵B,相邻两个整数之间用一个空格隔开。每个整数表示加农势力存在的毫秒数(最小曼哈顿距离值)

 

输入样例 1 

3 4
0001
0011
0110

输出样例 1

3 2 1 0
2 1 0 0
1 0 0 1
#include<bits/stdc++.h>
using namespace std;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int N=1010;
char g[N][N];
int d[N][N],n,m;
typedef pair<int,int> PII;
queue<PII>q;  

void Build(int n,int m){
    memset(d,-1,sizeof(d));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            char c = getchar();
            while (c!='0' && c!='1'){
                c = getchar();
            }
            if(c=='1'){
                d[i][j]=0;
                q.push(make_pair(i,j));  //压入队列,多源广搜
            }
        }
}

void Print(int n,int m){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cout<<d[i][j]<<' ';
        cout<<endl;
    }
}

void bfs(){
    while(q.size()){  
        auto t=q.front();
        q.pop();

        int x=t.first,y=t.second;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && a<n && b>=0&&  b<m && d[a][b]==-1){  
                d[a][b]=d[x][y]+1;
                q.push({a,b});
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    Build(n,m);
    bfs();
    Print(n,m);
    return 0;    
}

腐烂的橘子

class Solution {
    int cnt;
    int dis[10][10];
    int dir_x[4]={0, 1, 0, -1};
    int dir_y[4]={1, 0, -1, 0};
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int> >Q;
        memset(dis, -1, sizeof(dis));
        cnt = 0;
        int n=(int)grid.size(), m=(int)grid[0].size(), ans = 0;
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid[i][j] == 2){
                    Q.push(make_pair(i, j));
                    dis[i][j] = 0;
                }
                else if (grid[i][j] == 1) cnt += 1;
            }
        }
        while (!Q.empty()){
            pair<int,int> x = Q.front();Q.pop();
            for (int i = 0; i < 4; ++i){
                int tx = x.first + dir_x[i];
                int ty = x.second + dir_y[i];
                if (tx < 0|| tx >= n || ty < 0|| ty >= m|| ~dis[tx][ty] || !grid[tx][ty]) continue;
                dis[tx][ty] = dis[x.first][x.second] + 1;
                Q.push(make_pair(tx, ty));
                if (grid[tx][ty] == 1){
                    cnt -= 1;
                    ans = dis[tx][ty];
                    if (!cnt) break;
                }
            }
        }
        return cnt ? -1 : ans;
    }
};

作者:LeetCode-Solution
链接:https://leetcode.cn/problems/rotting-oranges/solution/fu-lan-de-ju-zi-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

标签:cnt,tx,ty,int,bfs,grid,多源,dis
From: https://www.cnblogs.com/weinan030416/p/17115425.html

相关文章

  • ABC 272 D (BFS)
    ABC272D题意给定一个N*N的棋盘,棋子初始位置在(1,1),给定一个数M,棋子每步操作可以走到距离不超过M的位置,假设棋子在(i,j),则下一步(x,y)应满足(x-i)×(x-i)+(y-j)×(y-j)<=M思路这是加......
  • POJ--3669 Meteor Shower(bfs/稍微变通)
    记录21:372023-2-9http://poj.org/problem?id=reference:《挑战程序设计竞赛(第2版)》第二章练习题索引p135DescriptionBessiehearsthatanextraordinarymeteor......
  • 【CCCC】L3-004 肿瘤诊断 (30分),三维BFS
    problemL3-004肿瘤诊断(30分)在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。输入格式:输入第一行给出4个正......
  • CF #724(div2)B. Prinzessin der Verurteilung, BFS枚举
    problemB.PrinzessinderVerurteilungtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputI,Fischl,Prinz......
  • 【CCCC】L3-005 垃圾箱分布 (30分),Dijkstra跑n遍 = 多源最短路,emm
    problemL3-005垃圾箱分布(30分)大家倒垃圾的时候,都希望垃圾箱距离自己比较近,但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方,同......
  • 【codevs1077】多源最短路
    problemsolutioncodes//Floyd-wallshall模板#include<iostream>usingnamespacestd;intn,e[110][110];intmain(){ios::sync_with_stdio(false);cin>>n;for(......
  • POJ 3126 Prime Path 素数+BFS
    PrimePathTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 27754 Accepted: 15152DescriptionTheministersofthecabinetwerequiteupsetbythem......
  • bfs 实战-求连通分量个数
    bfs即广度优先搜索,等同于树的层序遍历,下面用一个题目来讲解题目:图的广度优先遍历问题描述已知无向图的邻接矩阵,以该矩阵为基础,给出广度优先搜索遍历序列,并且给出该无向......
  • 2023牛客寒假算法基础集训营6 (B 思维+二分)(D 字符串匹配dp)(E 生成树+思维)(I 思维+
    2023牛客寒假算法基础集训营6(B思维+二分)(D字符串匹配dp)(E生成树+思维)(I思维+bfs)B阿宁的倍数题目大意:给定一个长度为n的数组a,有q次操作。修改:数组末尾增加......
  • BFS求最短路径
     加农是罪的化身,所到之处污秽遍地。原先富丽堂皇的海鲁拉城堡也被加农污秽了。根据调查,加农污秽一片地区有如下规律:下图是一个矩形区域,Y=3,X=4。 "."表示干净区域,而"......