H - 遥远的糖果 HihoCoder - 1478

给定一个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

思路

• 题意：给我们一个$n*m$n∗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;
}