AcWing 173.矩阵距离

HYLW · 2024-05-05 15:23:41 · 题解

• 题目描述

给定一个 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\limits_{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，相邻两个整数之间用一个空格隔开。

• 数据范围

• 输入样例：

3 4
0001
0011
0110

• 输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

• 代码样例：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int ans[N][N];
bool st[N][N];
struct node{
    int x,y;
};

void bfs(){
    queue<node> q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ans[i][j]==0)
                q.push({i,j}),st[i][j]=1;
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    while(!q.empty()){
        node u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=u.x+dx[i],y=u.y+dy[i];
            if(ans[x][y]!=-1)   continue;
            if(x<1 || x>n || y<1 || y>m)    continue;

            ans[x][y]=ans[u.x][u.y]+1;
            q.push({x,y});
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        char c[m+3];
        scanf("%s",c+1);
        for(int j=1;j<=m;j++)
            if(c[j]=='1')   ans[i][j]=0;
            else    ans[i][j]=-1;
    }

    bfs();

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",ans[i][j]);
        puts("");
    }
    return 0;
}