原题链接

题目描述

给定一个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]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}{dist(A[i][j],A[x][y])}$$
输入格式
第一行两个整数n,m。

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

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

数据范围
$1≤N,M≤1000$

样例

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

搜索+性质探索

这道题目我们主要要注意转换原题,原题告诉我们要求最短路,这个我们不能改变,但是原题说让我们求每个数与1的距离,那么我们只需要记住一点,那就是BFS具有层次单调性,且最重要的是天生自带flood-fill问题的解法.

flood-fill问题:一个起点到其他位置的最少步数.

这道题目我们完全可以认为是多起点问题,也就是说,我们直接将所有为1的点,加入到状态队列之中,那么这道题目就解决了.

C++ 代码

//重点部分写注释
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
using namespace std;
const int N=1100;
queue<pair<int,int> >q;//p.first为x坐标,p.second为y坐标
pair<int,int> now;//队列中临时坐标
int a[N][N],n,m,d[N][N];//定义地图a,最短路径地图d
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//上下左右四个方向的坐标变换
bool check(pair<int,int> Next)
{
    int x=Next.first,y=Next.second;//x坐标,y坐标
    if (x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1)//坐标在地图内,而且这个点没有被拓展过
    {
        d[x][y]=d[now.first][now.second]+1;//上一步+1,更新步数
        return true;
    }
    return false;
}
int main()
{
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char ch=getchar();
            a[i][j]=ch-'0';//字符变成数字
            d[i][j]=-1;//顺便初始化d数组,初始都为-1
            if (a[i][j])//这个点是1
            {
                d[i][j]=0;//自然是为0.
                q.push(mk(i,j));//将这个点加入到状态队列之中,因为它为可拓展点
            }
        }
        getchar();//读入换行符
    }
    while(q.size())//队列不空
    {
        now=q.front();//取出队头
        q.pop();//用完就出队
        for(int i=0;i<4;i++)
        {
            pair<int,int> Next=mk(now.first+dx[i],now.second+dy[i]);//x坐标进入下一步,y坐标进入下一步
            if (check(Next))//检测是否合法
                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;
}