矩阵距离——广度优先搜索

题目描述

给定一个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])}

即求与每个位置曼哈顿距离最近的1

N,M≤1000。

输入格式

第一行两个整数n,m。

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

输出格式

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

输入输出样例

输入样例1：复制

3 4
0001
0011
0110

输出样例1：复制

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

【耗时限制】2000ms 【内存限制】128MB

这道题如果一个一个枚举，就会超时,要mn个bfs，时间复杂度O(mn*mn)

就像这样，全TLE,0分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=1e3+5;
int n,m;
int vis[N][N],a[N][N],dis[N][N];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
struct node{
    int x,y;
};
int bfs(int x,int y){
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    queue<node> q;
    q.push((node){x,y});
    if(a[x][y]==1) return 0;
    vis[x][y]=1;
    dis[x][y]=0;
    while(!q.empty()){
        node f=q.front();q.pop();
        for(int i=0;i<4;i++){
            int u=f.x+dx[i],v=f.y+dy[i];
            if(u>=1&&u<=n&&v>=1&&v<=m&&!vis[u][v]){
                dis[u][v]=dis[f.x][f.y]+1;
                if(a[u][v]) return dis[u][v];
                q.push((node){u,v});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=1;j<=m;j++){
            a[i][j]=s[j-1]-'0';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<bfs(i,j)<<" ";
        }
        cout<<endl;
    }
    return 0;
}

应该所有1都入队列，只用一个bfs,时间复杂度O(mn)

这是正确的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=1e3+5;
int n,m;
int vis[N][N],a[N][N],dis[N][N];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
struct node{
    int x,y;
};
void bfs(){
    memset(vis,0,sizeof(vis));
    queue<node> q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==1){
                q.push((node){i,j});
                vis[i][j]=1;
            }
        }
    }
    while(!q.empty()){
        node f=q.front();q.pop();
        for(int i=0;i<4;i++){
            int u=f.x+dx[i],v=f.y+dy[i];
            if(u>=1&&u<=n&&v>=1&&v<=m&&!vis[u][v]){
                dis[u][v]=dis[f.x][f.y]+1;
                vis[u][v]=1;
                q.push((node){u,v});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=1;j<=m;j++){
            a[i][j]=s[j-1]-'0';
        }
    }
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<dis[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}