BZOJ2252: [2010Beijing wc]矩阵距离【bfs】

dzy posted @ 2013年6月10日 17:34 in BZOJ with tags BZOJ bfs , 1980 阅读

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

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

把所有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;
}
Avatar_small
ekhan.net 说:
2023年6月08日 20:41

How to Update/Renew Your Cell Phone Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. The bank has been offering a variety of handy ekhan.net services and amenities to its public banking clients. Registration for Indian Overseas Bank (IOB) Mobile Banking, How to Update/Renew Your Cell Phone Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. The bank has been offering a variety of handy services and amenities to its public banking clients. Registration for Indian Overseas Bank (IOB) Mobile Banking.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter