矩阵距离

题目

题目描述

假设我们有矩阵,其元素值非零即1

a11........a1m
...................
...................
an1........anm

定义aij与akl之间的距离为D(aij,akl)=abs(i-k)+abs(j-l)

输入

输入文件的第一行为两个整数，分别代表n和m。
接下来的n行，第i行的第 j个字符代表aij

输出

输出包含N行，每行M个用空格分开的数字，其中第i行第j个数字代表
Min(D(aij,axy)) 其中1<=x<=N 1<=y<=M,且axy=1

样例输入

样例输出

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

数据范围

1≤N,M≤1000

分析

一般人看到题后首先的想法一定是暴力。结果n^2m^2的时间复杂度轻松T掉，我也一样。于是有了广搜的思路(https://www.jianshu.com/p/bff70b786bb6)。若一个位置是1，则输出0。若是1，开始广搜，直到搜到离此点最近的1。然后求出D(aij,akl)=abs(i-k)+abs(j-l)。这保证值最小。代码如下。

#include <bits/stdc++.h>
using namespace std;
 
int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char a[1005][1005];
queue<int> q1;
queue<int> q2;
inline int bfs(int x,int y)
{
    q1.push(x);
    q2.push(y);
    while(!q1.empty()&&!q2.empty())
    {
        int qx=q1.front();
        int qy=q2.front();
        q1.pop();
        q2.pop();
        if(a[qx][qy]=='1') 
        {
            return abs(x-qx)+abs(y-qy);
        }
        for(int i=0;i<4;i++)
        {
            if(qx+dx[i]>n || qy+dy[i]>m || qy+dy[i]<=0 || qx+dx[i]<=0) continue;
            //if(x==3&&y==4) cout<<qx<<' '<<qy<<endl;
            q1.push(qx+dx[i]);
            q2.push(qy+dy[i]);
        }
         
    }
}
 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='1') cout<<0<<" ";
            else
            {
                while(!q1.empty()&&!q2.empty())
                {
                    q1.pop();
                    q2.pop();
                }
                cout<<bfs(i,j)<<" ";    
            }
        }
        cout<<endl;
    }
    return 0;
}

然后...............................................................................................就MLE了。

给大家一组数据，可以试试。

30 30

000000000000000000000000000000
000000000000000000000000000000
000000000001000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000

我的内心是崩溃的，要不是某李**拉着我我就把电脑砸了。

正当我绝望之时，大佬(他的博客：https://www.cnblogs.com/chenjiaxuan/)告诉我了一个方法。

这个方法与我的广搜相反。他没有广搜所有0，因为这样有几个0就要搜几次。他从1开始搜，搜所有的0并记录。于是时间复杂度就到了nm。代码如下

#include <bits/stdc++.h>
using namespace std;
int n,m,ans[1005][1005];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char a[1005][1005];
queue<int> q1;
queue<int> q2;
inline void bfs()
{
    while(!q1.empty()&&!q2.empty())	
    {
        int x=q1.front();
        int y=q2.front();
        q1.pop();
        q2.pop();
        for(int i=0;i<4;i++)
        {
        	int tx=x+dx[i],ty=y+dy[i];
            if(tx>n || ty>m || ty<=0 || tx<=0 || a[tx][ty]=='1' || ans[tx][ty]<=ans[x][y]+1) continue;
            ans[tx][ty]=ans[x][y]+1;
            q1.push(tx);
            q2.push(ty);
        }
    }
}
 
int main()
{
	memset(ans,999999,sizeof(ans));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='1')
			{
				q1.push(i);
				q2.push(j);
				ans[i][j]=0;
			}
		}
	bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cout<<ans[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}
/*
30 30
000000000000000000000000000000
000000000000000000000000000000
000000000001000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
*/

我永远也忘不了那个AC的瞬间