矩阵距离
题目 矩阵距离
思路分析
题意理解了就好写
给一个由 0 1 组成的矩阵
求矩阵中，各个点到 1 的 最短曼哈顿距离。
如果矩阵中只有 1 个 1，直接从 1 开始进行 bfs，就能求出各个点到 1 这个点的曼哈顿距离。
有多个 1，需将所有的 1 设置为起点进行 bfs
转变成上题差不多的意思 也就是多源 bfs
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=1010;
char g[N][N];
int d[N][N];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n-1 && y>=0 && y<=m-1 && d[x][y]==-1;
}
queue<PII> q;
void bfs(){
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny)){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>g[i];
memset(d,-1,sizeof d);
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;
}
}
}
bfs();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
💬 评论