hihocoder-1478 陆地到水域的最短距离
给定一个N x M的01矩阵,其中1表示陆地,0表示水域。对于每一个位置,求出它距离最近的水域的距离是多少。
矩阵中每个位置与它上下左右相邻的格子距离为1。
Input
以下N行每行M个0或者1,代表地图。
数据保证至少有1块水域。
对于30%的数据,1 <= N, M <= 100
对于100%的数据,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
显然是BFS裸题了,不过注意一点,一次性把所有起点压入队列,不然会tle
。
我记得上次出过原题,我就是BFStle
了无数发,然后用DP写了,DP的话也很简单,从两个对个角遍历一遍即可。
AC代码:
1 |
|