题目在这里
题目意思是这样的,一个人起始位置在 '@' 处,他在途中能到达的地方为 ' . ' 而 '#' 是障碍物,他不能到达。
问途中他所有能到达的 '.'的数量是多少 ??当然,他自己本身也算一个能到达的点。
其中两个样例的结果是这样的走出来的,这是"显而易见"的,哈哈~当然,当图很大的时候,数起来就能费事了。
所用的这个方法叫做FlooFill(洪水覆盖),从它名字来看就是个很暴力直接的方法,只要我能到的地方,我都用水把你淹没了。可以联想一下,在田地里用水渠灌溉田地时,只要你把要灌溉的地方挖好水道,最后,只要打开总的水闸开关,那么所有你想灌溉的田里最后都会有水进去。那个水闸就是这里的@点了。
再看百度百科的解释
画图的填充就是这么来的,通俗的来说,无孔不入。所以,我把这个题看做画图填充,用这个方法做肯定不会错了。
由于存在计数问题,所以稍微处理下,首先将每个'.'看做是oldColer,即我还没填充到它,后面,就对所有我没填充到的点(颜色为oldColor的)并且是我能到达的点进行填充(一定是能到达的才能),把它变为(newColor1),每成功的涂色一次,就把计数加1,这样,就不存在计数问题了。
再对每个格子进行扩展填充时,可以有这上述两种填充方法(有点尴尬,我画图竟然没找到颜色填充。。。。)
然后每扩充一个格子,就再以那个格子为起点,继续扩充,即递归的填充,直到所有的格子都被填完。
1 /*************************************************************************
2 > File Name: poj1979.cpp
3 > Author: YeGuoSheng
4 > Description:
5 man at @,Q:how many points('.') he can arrive
6 #:can not be arrived
7 > Created Time: 2019年07月23日 星期二 16时32分10秒
8 ************************************************************************/
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include