矩阵距离

题目

给定一个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的点全部加入队列,然后进行广搜即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std; 
const int N=1e3+5;
typedef pair<int,int> PII;

int dis[N][N];
int n,m;
char g[N][N]; 

void bfs(){ // 广搜 
    queue<PII> q;
    memset(dis,-1,sizeof dis);
    for(int i=0;i<n;i++){ //为1的点全部加入队列 
        for(int j=0;j<m;j++){ //并且距离为零 
            if(g[i][j]=='1'){
                dis[i][j]=0;
                q.push({i,j});
            }
        }
    }

    int dt[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
    while(!q.empty()){ // 广搜 
        auto t=q.front();
        q.pop();

        int x=t.first,y=t.second;
        for(int i=0;i<4;i++){
            int dx=x+dt[i][0];
            int dy=y+dt[i][1];
            if(dx>=0&&dx<n&&dy>=0&&dy<m&&dis[dx][dy]==-1){
                dis[dx][dy]=dis[x][y]+1;
                q.push({dx,dy});
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>g[i];
    bfs();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<dis[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

   转载规则


《矩阵距离》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
矩阵 矩阵
给定一个M行N列的01矩阵(只包含数字0或1的矩阵),再执行Q次询问,每次询问给出一个A行B列的01矩阵,求该矩阵是否在原矩阵中出现过。
2019-08-25
下一篇 
可达性统计 可达性统计
给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。
2019-08-21
  目录