本文主要是介绍AGC033 A - Darker and Darker(bfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
解法:
将所有黑色方块丢入队列中,bfs每次向四个方向扩展即可,
最后答案是扩展的次数.
code:
#include<bits/stdc++.h>
#define int long long
#define PI pair<int,int>
using namespace std;
const int maxm=1e3+5;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char s[maxm][maxm];
int mark[maxm][maxm];
int n,m;
void solve(){cin>>n>>m;queue<PI>q;for(int i=1;i<=n;i++){cin>>(s[i]+1);for(int j=1;j<=m;j++){if(s[i][j]=='#'){q.push({i,j});mark[i][j]=1;}}}int now=-1;while(q.size()){now++;int len=q.size();while(len--){PI t=q.front();q.pop();int x=t.first,y=t.second;for(int k=0;k<4;k++){int xx=x+dx[k],yy=y+dy[k];if(xx<1||xx>n||yy<1||yy>m)continue;if(mark[xx][yy])continue;mark[xx][yy]=1;q.push({xx,yy});}}}cout<<now<<endl;
}
signed main(){ios::sync_with_stdio(0);solve();return 0;
}
这篇关于AGC033 A - Darker and Darker(bfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!