传送门

Problem A. Mex Query

Problem B. Nim Game

Problem C. icebound 的账单

Problem G. 520

Problem H. 神殿

Problem J. icebound 的商店

Problem L. 跑图

文章目录

• 传送门
• • • • Problem A. Mex Query
      • Problem B. Nim Game
      • Problem C. icebound 的账单
      • Problem G. 520
      • Problem H. 神殿
      • Problem J. icebound 的商店
      • Problem L. 跑图
• Problem L. 跑图
• • • Description
    • Input
    • Output
    • Sample Input
    • Sample Output
  • 题目大意
  • 解题思路
  • AC代码

Problem L. 跑图

Time Limit: 1000ms
Memory Limit: 65536KB

Description

跑图是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​∣。

Input

第一行，有两个数 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

Output

n n n行，每行 m m m个数，表示某个点到离它最近的传送点的距离。

Sample Input

2 3
0 0 0
1 0 1

Sample Output

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 ⋯
直到队列为空，输出答案即可。

AC代码

#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