AcWing 173.矩阵距离

首先就是上一个时间超时的做法：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 1050
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts=INT_MAX;
char maps[MAX][MAX];
int dist[MAX][MAX];
int brr[MAX][MAX];
int a, b;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<PII>q;
vector<int>nextVisit;
void bfs(int x, int y) {
    memset(dist, -1, sizeof dist);
    q.push({ x,y });
    dist[x][y] = 0;
    while (!q.empty()) {
        auto  t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (dist[a][b] >= 0)
                continue;
            if (a<1 || a>n || b<1 || b>m)
                continue;

            q.push({ a,b });
            dist[a][b] = abs(x - a) + abs(y - b);
       }
    }
    if (maps[x][y] == '0') {
        _for(i, 1, n + 1) {
            _for(j, 1, m + 1) {
                    if (maps[i][j] == '1') {
                        counts = min(counts, dist[i][j]);
                    }
            }
        }
        brr[x][y] = counts;
    }
    else
        brr[x][y] = 0;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    _for(i, 1, n + 1) {
        _for(j, 1, m + 1)
            cin >> maps[i][j];
    }
    _for(i, 1, n + 1) {
        _for(j, 1, m + 1) {
            bfs(i, j);
            counts = INT_MAX;
        }
    }
    _for(i, 1, n + 1) {
        _for(j, 1, m + 1) {
            cout << brr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

具体原因不明，但是对于1000左右这里的数是不适用的，其他情况下都是可以的。

后来看了题解之后试着优化了一下。

其实和上面的思路是一样的，就是对于每一个点都进行遍历BFS，算出到各自点的距离，之后，再统一处理b矩阵，直接把距离最短的放里面。

但这样处理好像会很费劲，对于多个数组进行赋值和交换和变值，会超出时间限制也是正常的。

这里可以换一种思路进行优化：

说到底，如果对于某一点来说，这一点字符是’1‘，距离就直接是0了，不用担心。

如果是这一点字符是’0‘，那么我们需要计算这一点到’1‘的最短距离，其实换过来说，也就是所有字符是’1‘到达这一点的距离的最小值，也就是多源BFS的问题，所有’1‘字符同时扩散，看看各自的点距离。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 1050
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts=INT_MAX;
char maps[MAX][MAX];
int dist[MAX][MAX];
int brr[MAX][MAX];
int a, b;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<PII>q;
vector<int>nextVisit;
void bfs() {
    memset(dist, -1, sizeof dist);
    _for(i, 1, n + 1) {
        _for(j, 1, m + 1) {
            if (maps[i][j] == '1')
            {
                q.push({ i,j });
                dist[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        _for(i, 0, 4) {
            int a = dx[i] + t.first;
            int b = dy[i] + t.second;
            if (a<1 || a>n || b<1 || b>m)
                continue;
            if (dist[a][b] >= 0)
                continue;
            
            q.push({ a,b });
            dist[a][b] = dist[t.first][t.second] + 1;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    _for(i, 1, n + 1) {
        _for(j, 1, m + 1)
            cin >> maps[i][j];
    }
    bfs();
    _for(i, 1, n + 1) {
        _for(j, 1, m + 1) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}