UVAOJ705

UVAOJ705

705 – Slash Maze Time limit: 3.000 seconds

Slash Maze

By filling a rectangle with slashes (/) and backslashes ( ), you can generate nice little mazes. Here is an example:

As you can see, paths in the maze cannot branch, so the whole maze only contains cyclic paths and paths entering somewhere and leaving somewhere else. We are only interested in the cycles. In our example, there are two of them.

Your task is to write a program that counts the cycles and finds the length of the longest one. The length is defined as the number of small squares the cycle consists of (the ones bordered by gray lines in the picture). In this example, the long cycle has length 16 and the short one length 4.

Input 

The input contains several maze descriptions. Each description begins with one line containing two integers w and h ( ), the width and the height of the maze. The next h lines represent the maze itself, and contain w characters each; all these characters will be either /” or \“.

The input is terminated by a test case beginning with w = h = 0. This case should not be processed.

Output 

For each maze, first output the line Maze #n:”, where n is the number of the maze. Then, output the line kCycles; the longest has length l.”, where k is the number of cycles in the maze andl the length of the longest of the cycles. If the maze does not contain any cycles, output the line There are no cycles.“.

Output a blank line after each test case.

Sample Input 

Sample Output 

---

Miguel A. Revilla
2000-02-09

好烦的一道题目!

题意就是说求输入里面有几个闭环以及最大的闭环面积是多少~

光看着杠杠肯定是看不出名堂的，首先把输入数据处理一下，把

分别转化成

正好题意里面每一条杠杠是等于两个单位，所以这里转化过后真好一个点就对应一个面积单位，然后就是找闭环了，自然是用DFS搞一搞，不过这个地方得注意一下的就是在斜方向遍历的时候有一定的限定条件：

比如grid[row][col]（row为行数，col为列数, 0 <= row <= 2h-1 0 <= col <= 2w-1）要移动到grid[row-1][col-1]的时候就必须满足

或者

其他三个斜方向同理。