正在纠结这类水题有没有写题解的必要？

暴露智商了。囧。我智商-∞岂会轻易告诉你们？

把所有1的点放进队列。bfs。没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mp make_pair 
#define qsize 2000000
typedef pair<int,int> pii; pii q[qsize];
int head=0,tail=0,n,m,d[1005][1005];    char s[1005];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int main(){
    scanf("%d%d",&n,&m);    memset(d,63,sizeof(d));
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++) if(s[j]-'0') q[tail++]=mp(i,j), d[i][j]=0;
    }while(head!=tail){
        pii u=q[head++]; if(head>=qsize) head-=qsize;
        for(int k=0;k<4;k++){
            int xx=u.first+dx[k],yy=u.second+dy[k];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&d[u.first][u.second]+1<d[xx][yy]){
                d[xx][yy]=d[u.first][u.second]+1;
                q[tail++]=mp(xx,yy); if(tail>=qsize) tail-=qsize;
            }
        }
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) printf("%d ",d[i][j]);
        printf("\n");
    }return 0;
}

• 相关文章