分析
关于这类问题,我有一个很形象的比喻来理解:把目标点看成每次扩展蔓延一个格子的火
(这里的$扩展$指$bfs$中对每个点的扩展)
就拿这题来说吧:
可以把1
看成火
,那么对于第一次扩展,所有的火都向外蔓延一格,最新被火烧到的地方它的距离就是$1$,
类似地,如果火继续烧(即继续扩展),那么新覆盖的距离就是先前火的距离$+1$
- 例子(样例解释):(其中?表示待求距离,一开始
1
的位置自然距离是$0$)
$开始$
? ? ? 0
? ? 0 0
? 0 0 ?
$next$
? ? 1 0
? 1 0 0
1 0 0 1
$next$
? 2 1 0
2 1 0 0
1 0 0 1
$next$
3 2 1 0
2 1 0 0
1 0 0 1
$结束~$
是不是很直观^3^
代码:
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define SET0(a) memset(a,0,sizeof(a))
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DWN(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
typedef long long ll;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 1005;
int dis[N][N];
int mp[N][N];
int n,m;
void bfs(){
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
queue<PII> que;
FOR(i,1,n)
FOR(j,1,m){
if(mp[i][j]==1) {
que.push({i,j});
dis[i][j]=0;
}
}
while(!que.empty()){
PII hd=que.front();
que.pop();
FOR(i,0,4-1){
int kx=hd.x+dx[i];
int ky=hd.y+dy[i];
if(kx<1||kx>n||ky<1||ky>m) continue;
if(dis[kx][ky]!=-1) continue;
que.push({kx,ky});
dis[kx][ky]=dis[hd.x][hd.y]+1;
}
}
}
int main(){
cin>>n>>m;
FOR(i,1,n)
FOR(j,1,m){
char ch; cin>>ch;
if(ch=='1') mp[i][j]=1;
else mp[i][j]=0;
}
memset(dis,-1,sizeof dis);
bfs();
FOR(i,1,n){
FOR(j,1,m)
cout<<dis[i][j]<<' ';
cout<<endl;
}
return 0;
}