题目描述

给定一个N行M列的01矩阵A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：

dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个N行M列的整数矩阵B，其中：

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数n,m。

接下来一个N行M列的01矩阵，数字之间没有空格。

输出格式
一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。

数据范围
1≤N,M≤1000

难度：简单
时/空限制：1s / 64MB
总通过数：1425
总尝试数：2420
来源：《算法竞赛进阶指南》, 小马智行面试题
算法标签

样例

输入样例：
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1

(算法)

Flood Fill

时间复杂度

参考文献

<<算法提高课>>

C++ 代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII ;
const int N = 1100;
queue<PII>q;
int a[N][N],d[N][N];
int n,m;
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};
PII now;
int main()
{
    scanf("%d %d\n",&n,&m);
    for(int i = 1 ; i <= n; i ++ )
    {
        for(int j = 1 ; j <= m; j++)
        {
            char t = getchar();
            a[i][j] = t - '0';
            d[i][j] = -1;
            if(a[i][j])
            {
                d[i][j] = 0;
                q.push(make_pair(i,j));
            }
        }
        getchar();
    }
    while(q.size())
    {
        now = q.front();
        q.pop();
        for(int i = 0; i < 4;  i ++ )
        {
            PII next = make_pair(now.x + dx[i],now.y+dy[i]);
            int x1 = next.x,y1 = next.y;
            if(x1>=1&&x1 <= n&&y1 >= 1 && y1 <= m && d[x1][y1]==-1)
            {
             d[x1][y1] = d[now.x][now.y] + 1;
             q.push(next);
            } 
        }
    }

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1 ; j <= m;  j ++ )
         cout << d[i][j] << " ";
         cout << endl;
    }

    return 0;
}