说明：个人BFS成长感悟，只有第三个算法正确。

题目描述

计算一个矩阵中0到1之间的最短曼哈顿距离。

输入格式
第一行两个整数 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 0找1

全部BFS(超时)

遍历矩阵中每一个元素，如果为0，则开始BFS搜索距离最近的1，并计算曼哈顿距离，保存至答案数组。

C++ 代码

#include<iostream>
#include<queue>
#include<string>
using namespace std;
queue<int> q;
string s[1000+10];
int a[1000+10][1000+10],ans[1000+10][1000+10],N,M,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},x,y;
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++)
        cin>>s[i];
    for(int i=0;i<N;i++) 
        for(int j=0;j<M;j++)
            a[i][j]=s[i][j]-'0';      //处理输入矩阵
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(a[i][j]==1){            //如果为1，则距离为0
                ans[i][j]=0;
                continue;
            }
            int is[N][M];
            for(int n=0;n<N;n++)
                for(int m=0;m<M;m++)        //初始化标记数组
                    is[n][m]=0;
            q.push(i*M+j);
            while(!q.empty()){
                for(int k=0;k<4;k++){
                    x=q.front()/M,y=q.front()%M;
                    if(x+dx[k]<N&&x+dx[k]>-1&&y+dy[k]<M&&y+dy[k]>-1&&is[x+dx[k]][y+dy[k]]==0){
                        if(a[x+dx[k]][y+dy[k]]==0){
                            q.push((x+dx[k])*M+y+dy[k]);
                            is[x+dx[k]][y+dy[k]]=1;
                        }else{                  //找到最近的1
                            ans[i][j]=abs(x+dx[k]-i)+abs(y+dy[k]-j);
                            while(!q.empty())
                                q.pop();            //清空队列
                            break;
                        }

                    }
                    if(k==3&&!q.empty()){
                        q.pop();
                    }
                }
            }

        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cout<<ans[i][j]<<" ";           //输出答案
        cout<<endl;
    }
    return 0;
}

算法2 1找0

多次BFS（仍超时）

从所有的1位置开始BFS搜索，保存矩阵中到所有0的曼哈顿距离（并更新取最小）。

C++ 代码

#include<iostream>
#include<queue>
#include<string>
using namespace std;
queue<int> q;
string s[1000+10];
int a[1000+10][1000+10],ans[1000+10][1000+10],N,M,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},x,y;
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++)
        cin>>s[i];
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            a[i][j]=s[i][j]-'0';          //处理输入数据
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(a[i][j]==1){               //只对矩阵中的1进行BFS搜索
                ans[i][j]=0;
                int is[N][M];
                for(int n=0;n<N;n++)
                    for(int m=0;m<M;m++)
                        is[n][m]=0;         //更新标记数组
                q.push(i*M+j);
                while(!q.empty()){
                    for(int k=0;k<4;k++){
                        x=q.front()/M,y=q.front()%M;
                        if(x+dx[k]<N&&x+dx[k]>-1&&y+dy[k]<M&&y+dy[k]>-1&&is[x+dx[k]][y+dy[k]]==0){
                            if(a[x+dx[k]][y+dy[k]]==0){
                                q.push((x+dx[k])*M+y+dy[k]);
                                is[x+dx[k]][y+dy[k]]=1;
                                if(ans[x+dx[k]][y+dy[k]]==0)
                                    ans[x+dx[k]][y+dy[k]]=abs(x+dx[k]-i)+abs(y+dy[k]-j);
                                else{
                                    if(ans[x+dx[k]][y+dy[k]]>abs(x+dx[k]-i)+abs(y+dy[k]-j))
                                        ans[x+dx[k]][y+dy[k]]=abs(x+dx[k]-i)+abs(y+dy[k]-j);        //更新曼哈顿距离
                                }
                            }

                        }
                        if(k==3){
                            q.pop();
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

算法3 1找0

一次多源BFS（同时搜）

将所有的1位置入队列，共视为一次BFS,并向外找0（只找一层），标记，入队，更新（具体更新见代码）

C++代码

#include<iostream>
#include<string>
#include<queue>
using namespace std;
string s[1000+10];
int a[1000+10][1000+10],ans[1000+10][1000+10],x,y,N,M,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},is[1000+10][1000+10];
queue<int> q;
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++)
        cin>>s[i];
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            a[i][j]=s[i][j]-'0';
            if(a[i][j]==1)
                q.push(i*M+j);          //处理输入数据，并将所有1位置入队
        }
    while(!q.empty()){
        x=q.front()/M,y=q.front()%M;
        for(int k=0;k<4;k++){
            if(x+dx[k]<N&&x+dx[k]>-1&&y+dy[k]>-1&&y+dy[k]<M&&a[x+dx[k]][y+dy[k]]==0&&is[x+dx[k]][y+dy[k]]==0){
                ans[x+dx[k]][y+dy[k]]=ans[x][y]+1;  //更新（精髓），用前一位置的距离跟新下一位置的距离
                q.push((x+dx[k])*M+y+dy[k]);        //入队
                is[x+dx[k]][y+dy[k]]=1;             //标记
            }
            if(k==3) 
                q.pop();
        }

    }

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}