Time Limit: 1000ms
Memory Limit: 65536KB
跑图是RPG游戏中很烦躁的事情。玩家需要跑到距离他最近的传送点的位置。现在给你一张 N × M N \times M N×M的方格图,每个方格中数值 0 0 0表示为平地,数值 1 1 1表示为传送点,你的任务是输出一张 N × M N \times M N×M的矩阵, M a t r i x x y Matrix_{xy} Matrixxy表示从 ( x , y ) (x,y) (x,y)到距离它最近的传送点的距离。 这里的距离是曼哈顿距离, ( x 1 , y 1 ) → ( x 2 , y 2 ) (x_1,y_1) \rightarrow(x_2,y_2) (x1,y1)→(x2,y2)的距离为 ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1−x2∣+∣y1−y2∣。
第一行,有两个数 n , m n,m n,m。接下来 n n n行,每行 m m m个数。
数据保证至少有一个传送点。
1 ≤ n ≤ 500 1 \leq n \leq 500 1≤n≤500, 1 ≤ m ≤ 500 1 \leq m \leq 500 1≤m≤500
n n n行,每行 m m m个数,表示某个点到离它最近的传送点的距离。
2 3 0 0 0 1 0 1
1 2 1 0 1 0
给你个地图,每个点初始值为 0 0 0或 1 1 1。让你计算出每个点到任意一个 1 1 1的最近的距离。
这是一道广搜题。简单说一下:
我们以所有初始值为 1 1 1的点为起点,入队,它们所能到达且未到达过的点是它的值加一。
队列中的初始的点是所有出发点,凡是它们能一步到达(且未达到过)的地方,答案都是1。
然后这个能到达的地方就会被放到队尾,直到所有的出发点全部出队,就轮到答案是1的点了。
答案是1的点能够一步到达的且未到达过的点,答案都是2。之后它们也入队。
等所有答案都是1的点都出队后,该由答案为2的点为起点 ⋯ \cdots ⋯
⋯ \cdots ⋯
直到队列为空,输出答案即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; bool sf[510][510]={0};//是否出现过。没出现过用false,出现过用ture。 int a[510][510]={0};//最终要输出的地图的结果 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//每个点有4个方向:上下左右。dir是direction的缩写。{1,0}代表x+1,y+0 int main() { int n,m; cin>>n>>m; queue<pair<int,int> >q;//每个节点的pair<int,int>的两个数分别代表x和y for(int i=0;i<n;i++)//输入部分 { for(int j=0;j<m;j++) { int t; scanf("%d",&t); if(t)//如果t初始值是1 { sf[i][j]=1;//这一点答案就是0,已经走过 q.push(pair<int,int>(i,j));//入队 } } } while(q.size())//队列不空时 { pair<int,int>thisPair=q.front();//取出队首的元素 q.pop(); for(int i=0;i<4;i++)//4个方向 { int tx=thisPair.first+dir[i][0];//to x:要到的x的坐标 int ty=thisPair.second+dir[i][1];//t0 y:要到的y的坐标 if(tx>=0&&tx<n&&ty>=0&&ty<m&&!sf[tx][ty])//如果tx在[0,n)并且ty在[0,m)并且这一点还没有处理过 { sf[tx][ty]=1;//现在这一点处理过了 a[tx][ty]=a[thisPair.first][thisPair.second]+1;//这一点的值是上一点的值+1 q.push(pair<int,int>(tx,ty));//入队 } } } for(int i=0;i<n;i++)//打印 { for(int j=0;j<m;j++) { printf("%d ",a[i][j]);//输出 } puts("");//换行 } return 0; }
原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/116537689