D - 水陆距离 HihoCoder - 1478
给定一个N x M的01矩阵，其中1表示陆地，0表示水域。对于每一个位置，求出它距离最近的水域的距离是多少。
矩阵中每个位置与它上下左右相邻的格子距离为1。
Input
第一行包含两个整数，N和M。
以下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
分析:题目其实很容易理解.就是给一个N*M的矩阵.然后把除了0之外的点的值变成与其最近0的距离.
可能我头脑比较清奇.瞬间想到暴力:把每个0存下来,然后遍历每个非零点 然后比较取最小值(于是成功T了.)奈斯???
再分析:还是从0出发.可以发现这个值是从零周围扩散出去的.那么不难发现,这其实就是个bfs.
不错,是个bfs,从0的四个方向出发,然后再从扩展的四个方向出发,每次扩展,距离都+1.
思路:边输入边记录0的位置,然后对其初始化,存入队列.
接着,就是经典while循环从0扩散四个方向走队列了.
说的不太好,详情看代码注释.
代码:
#include
#include
#include
#include
#include
#include
#define M 805
using namespace std;
struct node
{
int x;
int y;
int dis;
};
struct node p;
string mm[M];
queue q;
int n,m,vis[M][M],ans[M][M],ne[4][2]={0,1,1,0,0,-1,-1,0};
int main()
{
cin>>n>>m;
for(int i=0;i>mm[i];//这里要注意一下样例输入点中间没空格...
for(int j=0;j=0&&xx=0&&yy
ps:wawawa2018年4月12日 11:04:23
暴力死T,广搜不会.花了一天来学用队列和广搜.
原来看过啊哈算法讲的广搜,现在觉得里面太基础太详细,所有的标准模版库里的容器函数都是用数组来模拟的.
虽然给人讲的很详细,但也只适合学基础,实用的话到不可能再用数组来模拟了.
这里推荐一本书<<算法笔记>>
个人觉得实用,虽然没有<<啊哈算法>>写的那么生动形象,也没有那么基础,但是讲的真的很实用,
怎么说呢,比较综合吧.适合有基础的看.
(滑稽脸)会有人看这个博客嘛..还推荐书...搞笑了...
因为渴望知识而学习,非名利.
京公网安备 11010802041100号