题目描述
给定一个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
样例
输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1
深搜
多元最短路问题,有多个起点,求到各个点的最短距离
看做边权都是1,就可以用dfs来做
与最短路同理,可以把多个起点看做是有一个虚拟起点与这些点间存在权值为0的边;再使用迪杰斯特拉算法,在队列中首先把所有距离为0的点都放进队列,再把为1的放进队列……
并且由于权值都是1,所以队列中的值一定是单调增的,也就不需要用优先队列去存储,深搜每个节点只计算一次,时间复杂度O(1)
第一次搜到某个节点得到的距离就是最短距离
C++ 代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005;
typedef pair<int,int>PII;//二维宽搜
int n,m;
char g[N][N];//记录矩阵
int d[N][N];//记录距离
void bfs(){
memset(d,-1,sizeof(d));
queue<PII>q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='1'){
q.push({i,j});
d[i][j]=0;
}
}
}
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
while(q.size()){
PII t=q.front();
int x=t.first,y=t.second;
q.pop();
for(int i=0;i<4;i++){
int a=x+dir[i][0];
int b=y+dir[i][1];
if(a>=0&&a<n&&b>=0&&b<m&&d[a][b]==-1){//如果没有越界并且这个点没有被访问过
d[a][b]=d[x][y]+1;
q.push({a,b});
}
}
}
}
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<<d[i][j]<<" ";
}
cout<<endl;
}
return 0;
}