HDU1312 - Red and Black
文章目录
链接:https://vjudge.net/problem/HDU-1312
Task
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. ‘.’ - a black tile ‘#’ - a red tile ‘@’ - a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample
input:
|
|
output:
|
|
Solution
建立两个二维数组,a用于存储输入字符串,b用于记录当前格子有没有被访问到。用递归实现深度优先搜索
。
在DFS函数中,对上下左右四个方向讨论,对应4个if分支。每一层递归对当前节点的上下左右四个节点分别讨论,如果可以走(未到边界,不是#,未被走过)就走过去,如果不能走就退出一层递归,即退回到上一个节点,以此类推。
如下图是DFS搜索过程的可视化,左边是第4个输入示例,右边是更复杂的一个例子。
|
|