BZOJ2252 矩阵距离

2014.12.22 12:21 Mon| 1 visits oi_2015| 2015_刷题日常| Text

Solution

显然,每一个元素的距离只能由与它相邻的元素的距离的最小值更新。那么这就是一道BFS的水题咯!

将值为1的元素设为BFS的起点,然后……乱搞即可

Code

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define inf 0x3f3f3f3f

char s[N][N];
int n,m,dis[N][N];
queue< pair<int,int> > q;
const int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};

void bfs()
{
    while(!q.empty())
    {
        int x=q.front().first, y=q.front().second;
        q.pop();
        for(int i=1;i<=4;i++)
            if(x+dx[i]&&y+dy[i]&&x+dx[i]<=n&&y+dy[i]<=m&&dis[x+dx[i]][y+dy[i]]==inf)
                dis[x+dx[i]][y+dy[i]]=dis[x][y]+1, q.push(make_pair(x+dx[i],y+dy[i]));
    }
}

int main()
{
    memset(dis,0x3f,sizeof dis);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j]=='1')
                dis[i][j]=0, q.push(make_pair(i,j));
    bfs();
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++)
            printf("%d ",dis[i][j]);
}