欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

H - 遥远的糖果 HihoCoder - 1478

程序员文章站 2022-05-24 08:48:39
...

给定一个N x M的01矩阵,其中1表示人,0表示糖。对于每一个位置,求出每个位置离糖的最短距离是多少。

矩阵中每个位置与它上下左右相邻的格子距离为1。

Input 第一行包含两个整数,N和M。

以下N行每行M个0或者1。

数据保证至少有1块糖。

1 <= N, M <= 800

Output 输出N行,每行M个空格分隔的整数。表示每个位置最近的糖离它的位置。

Sample Input
4 4  
0110  
1111  
1111  
0110
Sample Output
0 1 1 0  
1 2 2 1  
1 2 2 1  
0 1 1 0

思路

  • 题意:给我们一个nmn*m的二维举证,在这个矩阵上的元素由0、1构成,其中0代表糖果,1代表人,让求人到糖果所以到最短距离(相邻元素值的间隔是1)
  • 典型的bfs问题,我们把可以把所有糖????作为起点压入队列,我们在假设一个时间表tim[][],给这个时间遍元素初始化除了糖的所对应的位置其他都初始话为INF,用bfs去跑一下这个时间表,就可得出答案了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
using namespace std;

#define ll long long 
#define db double 
const int mxn = 1005;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;


int mov[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
int mp[mxn][mxn];
int tim[mxn][mxn];
int m, n;

struct Node
{
    int x, y, t;
} st, ed;
queue<Node> q;

void bfs()
{
    while(! q.empty())
    {
        st = q.front(); q.pop();

        for(int i = 0; i < 4; i ++)
        {
            ed.x = st.x + mov[i][1];
            ed.y = st.y + mov[i][0];
            ed.t = st.t + 1;
            if(ed.x >= 0 && ed.y >= 0 && ed.x < m && ed.y < n)
            {
                if(ed.t < tim[ed.x][ed.y])
                {
                    tim[ed.x][ed.y] = ed.t;
                    q.push(ed);
                }
            }
        }

    }
    for(int i = 0; i < m; i ++)
    {
        for(int j = 0; j < n; j ++)
            printf("%d ", tim[i][j]);
        printf("\n");
    }
}





int main()
{
    /* freopen("A.txt","r",stdin); */
    /* freopen("Ans.txt","w",stdout); */
    memset(tim, INF, sizeof(tim));
    scanf("%d %d", &m, &n);
    char ar[mxn][mxn];
    for(int i = 0; i < m; i ++)
    {
        scanf("%s", ar[i]);
        for(int j = 0; j < n; j ++)
        {
            if(ar[i][j] == '0')
                q.push( (Node){i, j, 0} ), tim[i][j] = 0;
        }
    }
    bfs();

    return 0;
}

相关标签: # 广度搜索

上一篇: Latex bug修正

下一篇: A. IQ test