当前位置：首页 > news >正文

AcWing 173.矩阵距离

news 来源：原创 2024/5/10 20:49:49

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

#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;}elsebrr[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;
}