跑图是RPG游戏中很烦躁的事情。玩家需要跑到距离他最近的传送点的位置。现在给你一张
N×MN imes M
N×M的方格图，每个方格中数值
00
0表示为平地，数值
11
1表示为传送点，你的任务是输出一张
N×MN imes MN×M的矩阵，MatrixxyMatrix_{xy}Matrixxy表示从
(x,y)(x,y)
(x,y)到距离它最近的传送点的距离。 这里的距离是曼哈顿距离，
(x1,y1)→(x2,y2)(x_1,y_1)
ightarrow(x_2,y_2)(x1,y1)→(x2,y2) 的距离为∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|∣x1−x2∣+∣y1−y2输入：
第一行，有两个数
n,mn,m
n,m。接下来
nn
n行，每行
mm
m个数。
数据保证至少有一个传送点。
1≤n≤5001 leq n leq 500
1≤n≤500，
1≤m≤5001 leq m leq 500
1≤m≤500
输出：
nn
n行，每行
mm
m个数，表示某个点到离它最近的传送点的距离。
--------------分割线-5/1-----------------------
题意:求出图中每一个点到最近的(曼哈顿距离)的传送点的距离.
题解:先保存所有的传送点,枚举每一个传送点搜索,如果某个点到某个传送点的距离小于原来保存的距离,那么我们就更新这个点.全部结束后,保存的就是最优解.
tips: 上面的题解写复杂了,划掉重写,优化前的代码放在了最后面---------5/2.
题解: 先保存所有的传送点,直接跑BFS,如果某个点到某个传送点的距离小于原来保存的距离,那么我们就 更新 这个点,并保存这个点. 全部结束后,保存的就是 最优解.
最优:
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
const int N=505;
int mp[N][N];
queue<P> q;
const int INF=0x3f3f3f;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(){
while(!q.empty()){
P now=q.front();q.pop();
int x,y;
for(int i=0;i<4;i++){
x=now.fir+dir[i][0];
y=now.sec+dir[i][1];
if(mp[x][y]>mp[now.fir][now.sec]+1) mp[x][y]=mp[now.fir][now.sec]+1,q.push({x,y});
}
}
}
int main(){
int n,m;
cin>>n>>m;
//memset(mp,-1,sizeof(mp));
int p;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&p);
if(p==1){
q.push({i,j});
mp[i][j]=0;
}
else
mp[i][j]=INF;
}
}
//queue<P>::iterator it=q.begin();
bfs();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("%d%c",mp[i][j],j==m?'
':' ');
return 0;
}
优化前:
#include <bits/stdc++.h>
using namespace std;
const int N=505;
//int mp[N][N];
int vis[N][N];
#define P pair<int,int>
queue<P> q;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(P now){
queue<P> qp;
qp.push(now);
while(!qp.empty()){
now=qp.front();qp.pop();
for(int i=0;i<4;i++){
int x=now.first+dir[i][0],y=now.second+dir[i][1];
if(vis[x][y]>vis[now.first][now.second]+1) vis[x][y]=vis[now.first][now.second]+1,qp.push({x,y});
//
}
}
}
int main(){
int n,m;
cin>>n>>m;
int p;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&p);
if(p==1) q.push({i,j}),vis[i][j]=0;
else vis[i][j]=0x3f3f3f;
}
}
P node;
while(!q.empty()){
node=q.front();q.pop();
bfs(node);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d%c",vis[i][j],j==m?'
':' ');
}
}
return 0;
}