705 - Slash Maze

[20717TZ]

705 Slash Maze WAsssssssssssssssssss
Help Me

[jaywinyeah]

I am suprised that no one has atleast talked about this problem. I will be the first, since I had trouble with it and found no solice on this board. The algorithm I used is by no means the only algorithm or even the best, but I will try to give hints as to my approach. I got accepted after four tries, so you can mostly trust what I am saying.

This problem was very hard at first to see the cycles visually. The example they use is very clear, but they draw a grid system that is slanted. One could try to implement the grid system of little boxes, but that would require that you turn the entire maze 45 degrees and the slashes would become horizontal and vertical lines. To do it that way is certainly feasable, but I would have hard time implementing such a scheme.

My approach is to leave the slashes in the current grid they are in and try to trace out every path. In fact, to see my approach more clearly, I suggest drawing a grid, the width and height of the sample, and then placing each slash in one cell of the grid. It should look the same as the sample, but each slash would be boxed in. Now, you can see that each cell is split into two halves by the slash that cuts diagonally through the box. Lets start in the left half of the very first box (upper-left corner) and put a one in that half. That box is a '\' which means that we can only go left or down. Since left is off the grid, we go down. This places us in the right half of the grid cell just bellow the first cell. Place another one in the right half of that cell. We can't go back the way we came, so the only option is to move to the right. Place another one in the left half of that cell. This process would continue until we either left the board (no cycle), hit a different number than our current number (no cycle), or hit the same number that we are filling our grid in with (cycle). Moreover, if you find a cycle, the cycle length is exactly equal to the number of halves that have the current number in them. It also equal to the number of steps it took to reach the current number from the other side, since each step fills in one half cell. Try it out on the grid you drew for more clearity.

I also found this problem hard to come up with test input, so here are the examples I used to test my program. The large one is just a random sample. If your program doesn't match the output for that example, it probably won't be accepted.

6 4
\//\\/
\///\/
//\\/\
\/\///
3 3
///
\//
\\\
5 5
/\/\/
\/\/\
/\/\/
/\/\/
\/\/\
4 4
//\\
//\\
\\//
\\//
6 6
/\/\/\
\//\\/
///\\\
\\\///
/\\//\
\/\/\/
6 4
/\/\/\
\\/\//
//\/\\
\/\/\/
6 4
/\/\/\
\\/\//
//\/\/
\/\/\/
0 1

1 0
75 75
\\\//\/\\/////\//\\\\\\/\//\\\\//\//////\\\/\//\/\\/\\/\/\//\/\/\\\/\/\\//\
//\\\/\/\\\//\/\\\/\/\/\\\/\/\/\\//\/\\\/\\/\/\//\\/\///////\//\/\\///\/\\/
/\\//\///\\\\/////\//\/\///\\\\/\//\/\\/\\\\\\/\////\\\\//\\////\/\\\/\/\\\
\\\//\\\/\\/\/\/\\/\/\\\\/\\\\//\\\/\/\\/\\\\\\\\/\\/\////\\//\\\//\/\///\\
/\\//\/\/\/\\\//\/\/\\/\\/\\\\\//\\/\\///\\/\\\///\\//\\///\//////\\//\/\\/
\\\\\//\\\\/\\/\///\\/\/\\/\///\////\/\\\/\\/\/\/\\\/\\\\/////\\\\//\\\\//\
\///\/\/\\//\\\\/\\\\//\/\//\\/\///\\\\\\\/\\\\/\/\\\//\\/\\//\///\/\\\//\/
\\/\\//////\//\\/\/\\\\\\//\\\\//\//\//\/\/\/\/\\//\\/\///\//\\\\\/\\//\\\\
//\\/\//\\//\//\//\/\\///\\/\/\////\\/\\///\////\/\\///\\/\///\\\\//\\/\///
\//\////\///\\\\\\\///\//\/\///\\/\/\\\\///\\\/\\\///\\\/\\//\\/\\/\//\/\\\
/\\//\\///\\\\\\///\////\///\/\/\\\//\\/\\/\////\/\\/\/\////\/\/\\/\/\/\/\/
/\/\\\\\/\\/\/\\/\\///\\//\//\/\//\//\////////\////\\/\\\\\\\///\\////\\/\\
/\//\\/\\\/\\/\//\\\\\/\\\////\//\\/\\\\\\\/////\\\////\/\\//\/\\\\\/\//\\\
\/\\/\//\\\//\/\\\/\\///\\\\\\\\/\\\//\\\///\\\/\\\/\\\\\\/\/\\/\/\/\/\/\/\
//\\//\\/\\//\\\\///\\\\\\\/\\///\\//\///\//////\/\//\/\\\\/\\/\//\\/\/\///
\\/\/\//\/\//\\///\\\\\/\///////////\///\\/\/\//\/\///\/\\\/\/\\/\\\\\/\\/\
///\\\\///\/\//\\\\\/\/\\\\///\\\/\\\\\\\\\\///\\\\\/\///\\/\/\///\\\\\\/\/
\//\\\\\/\////\\\/\\\/\\\\/\/\//\////\\//\//////\/\//\\/\///\/\/\\///\\///\
/\\/\\\\\\\\\\\\//\\\///\///\\/\\\\///\////\\///\//\/////\\\//\//\\/\\\/\\/
//\/////\\/\\\\/\\\/\\//\\\\\//////\//\\/\////\///\\\\//\////\/\/\/\///\//\
//\\\\\/\//\//\\\\\\///\\\/\/\////\/\/\\\\\/\///\/\\\///\\//\\\/\/\\//\/\/\
\\/\\\/\\//\///\\//\\\\\\/\/\\///////\/\//\\\/\\////\\\\\/\\\/\\/\/\////\\\
/\\//\\\\/\/\/\\/\\/\/\\///\////\\\//\/\\//\\/\///\/\\//\\/\////\//\\/\\\\\
\\/\//\\///\/\/\//\//\\\\\//\/\\/\/\//\\///////////////\/\\/\\\/\\\\/\\/\//
//\//\////\///\/\/\/\///\\//\\/\\//\//\\/\//\/\/\//\\\\\\///\/\\\\\\//\/\\/
\\//\//\\//\\/\\\\/\\\\\/\\/\\//\/\\\/\//\\\///\\/\\\/\\//\\/\\/\///\/\\\/\
/\//\//\/\\\/\\///\\\/\\/\/\\///\\\\///\//\/\\\\///\\\\/\\/\\\/\///\/\\\//\
\//\\//\///\/\/\\\\/\\/\\\\\\////\\\\/\\\///\\/\\/\\\\\\/\//\\/\\//\/\//\//
//\\\/\///\/\\\\\/\\//\////\\//\\//\/\//\\/////\\\/\\\/////\\//\/\/\\\/\\\/
//\/\\/////\\\\\\////\\\\/\\/\//\/\\//\\\//\/\///\\/\\\\//\///\//\///\/\\\/
//////\/\///\\\///////\\\/\/\\//\\\//\\\\\\/////\//\/\/////\\//\\/\/\/\/\/\
/\/\///\\//\///\\\\\/\\/\\////\/\/\/\//\//\\///\///\\/\/\/\/\\\\//\/\\\//\\
\\/\/\//\\\//\\//\///\\\/\\//\///\/\////\/\/\\\/\//\\\///\/\/\\/\///\\\///\
\//\//\\/\///\/\/\\/\/\\\\///\\/////\/\\///////////\/\\\\/\\\\\/\/////\///\
/\///\\\////\\\\/\/\\\///\//\\\\\\/\///\\//\//////\\/\\/\\\/\\\\\\/\//\\///
\/\////\/\///\\///\///\\\/\\\/\/\\/\/\\\\/\\\\/////\\\\////\///\\\/\///\\//
/\\//////\/\////\/\///\\\/\///\\\\//////\\/////\/\////\\/\/////\\//\//\\/\\
/\/\/\\///\\\\///\\//\/\/\/\////\//\//\\/\//\//\/\////\/\////\\/\//\\\\\/\\
/\\\\\/\/\/\/\\\/\\\//\\/\\/////\/\/\\//\\/\/\//\/\/\\////\//\//\/\\/\\\/\\
\\/\\\/\/\\\/\\\////////\\//\\/\///\/\/\////\//\\/\\\\\\\\//\\\\/\\\\\\/\//
//\/\/\//\/\/\/\\/\/\\/\\\/\//\//////\//\\\\\\\///\\/\//////\\/\\////\\\\/\
////\/\\/\\///\\\\///\/\//\\/\/\//\\/\//\/\\/\//////\//\/////\/\\\/\\/\\/\\
//\/\//\\/\//\/\\\\//\\//\/\//\\\///\//\\\///\\\\/\\//\\\\//\//\\\\/\\/\\/\
/\\\\////\\//\\\/\\\\\///\\\\\/\\\\\///\\\/\//\\\\//\\/\///////\/\//\\/////
//\\\\\\/\/\\/\\\/\/\\\\//\//\\/\\\\/\/\\\/\//\/\/\/\\\////\/\\///\/\/\//\\
///\/\///\\/\\/\/\/\///\//\///\////\\//\\/\/\//\\\////\////\////\\\\/\\///\
\\\//\//\\\\\//\//\\////\//\\///\/\/\\\/\//\/\\\//\\\/\\\\//\\/\//\//\/////
\/\\\\\\\\\/\//\\\/\\\\\/\\\/\\/\/\/\/\/\\\\/////\//\\\/\\\\\\/\\/\\\\\\/\/
//\/////\/\/\\///////\\//\\\\\\////\\////\/\//\///\\\\//\/\\\\\\\//\/\\\\//
\\/\/\\\//\//\\\//\/\\\\/\\/\\///////\///\\/\\\/\///\\///////\\\/\\\\\\\\//
\\//\/\//\\//\\//\\\\\\/\\\/\/\\/\\\\\//\\\\/\/\//\//\///\\\\/\\//\////\\\/
/\\/\/\//\//\\\/\//\\/\/\\\\\\/\\//\/\\/\\///\/\\\//\\//\\/\\\\////\//\\///
///\\\\/\/\\\\/\\///\\\//\/\//\//\\\//\\///\////\/\//\\\///\//////\\\\\/\\\
/\\\/\////\///\\\\///\\\\/\/\\\\\/\//\\/\\//////\\\\\/\\/\//\///\\/\\\/\\\/
\\\//\\\\\\/\\\//\\//\//\/\\//\\\////\\/\/\/\\/\\\///\///\/\\/\\\/\/\//\//\
\/\\\/////\\////\////\\\//\\/\\/\/\\\/\/\/\/\/\///\////\\\///\\//\/\/\//\\/
//\/\///\\//\/\\////\///\\/\////\/\///\\\//\//////\\\\\/\\/\\\/\\/\\\\\/\//
//\/\//\\/\///\\/\\///\///\//\/\\//////\//\\\\/\///////\\\////\\/\//\//\//\
//\\\/\\/\/\/\\/\/\/\//\\\/\//\//\\\\/\//\\\\\\/\////\\\/\\\/\\//\//\/\\\//
\/\\/\\\\/\//\/\\/\/\\\//\\\\/\//\\/\/\\\\\///\\\\\/\\\/\/\\/\\\\\\/\/\/\/\
\\///\/\/\///\/\\\\\/\\/\//////\/\///\/\/\\/\/\\//\/\//\//\\\\/\\\\///\/\/\
/\/\/\\\\/\///\\/\/\\/\/\\\\/\/\/\//\\\\\/////\//\\//\\/\\\///\\\//\\\/\\\\
/\\\\//\///\//\/////\/\\/////\/\/\\\\/\\//\//\\\\\/\////\\\\/\\/\////\\\//\
\/\/\///\//\\\\\/\\\\\///\//\\////\\\\\/\/////\\\/\\//\\\///\///\//\///\\\/
\///\\\////\/\\/\/\\//\/\////\\\\/\\\/\\/\\\\\\\//\\////\/\\\\\\///\//\/\//
/\/\//\///\//////\\\/\\/\///\/\/\//\\/\/\\////\\\\\\/\/\\\//\/\\/\\\/\//\\\
/\\//\\\//////\\/\\///\/\/\\/\/\////\\/\\\/\\//////////\///\/\\/\\\/\\\\/\/
///\//\/\\//\/\//\//\///////\\\//\\\\//\/\/\\//\\/\//////\\\\\\\///\/\\/\//
\\///\/\\\/\//\///\\\\\\/\\\\/\\/\\//\/\\\/\\\/\/\//\///\\///\/\///\////\/\
\////\\////\\/\\\/\/\///\///\//\/\/\\/\/\/\\\///\\\\\///\/\\\/\\/\/\\\/\//\
\\\/\/\\////\\///\//\\\\/\/\\\//\//\////\/\//\/\\\\\/\//\/\//////\\/\\//\\\
\////\\\/////\\\//\\\\//\\\\//\\/\\\\//\/\/\\\\/\///\//\\//\\\\//\/\//////\
\\\\\//\\\/\\/\////\\//\\//\/\/\/\/////\\/\\//\///\\/\//\\\\\\\///\/\//\/\\
/\/\\//\//\/\\\/////\\\/\\\//\//\////\\///\/\//\\\\\/\/\//////\\/\\/\\/\///
\/\//\//\//\\///\\\//\\////////\\\\//\//\//\\\/\\///\/\/\/\///\/\////\/\\\/
5 5
//\\\
///\\
\\\\\
/\\//
\\\//
0 0

Output:

Maze #1:
2 Cycles; the longest has length 16.

Maze #2:
There are no cycles.

Maze #3:
6 Cycles; the longest has length 4.

Maze #4:
2 Cycles; the longest has length 12.

Maze #5:
7 Cycles; the longest has length 20.

Maze #6:
2 Cycles; the longest has length 28.

Maze #7:
1 Cycles; the longest has length 4.

Maze #8:
There are no cycles.

Maze #9:
There are no cycles.

Maze #10:
586 Cycles; the longest has length 1128.

Maze #11:
1 Cycles; the longest has length 24.


I hope this helps. I will leave the implementation up to you. Good luck.

[wos]

What i did is to represent the boxes as a graph (adjacency lists in matrices) and then use DFS to find and count the cycles in that graph, and i used flood fill for counting the length of those cycles...

[daveon]

You can convert the 45 slanted representation to the 90 straight representation.
Just redraw the sample input on paper and rotate the paper.
You can easily represent walls with 4 booleans for each cell.
Once you have the walls, just flood fill.

Good luck.

[Khaled_912]

You can have an implicit graph of size w*3 and h*3, where each slash occupies a 3x3 field inside your matrix.
A '\' should occupy 3 sectors diagonaly from left to right, while the '/' from the right to left.
Here's a snippet for filling the array:
bool a[250][250];
...
...
...
for (i=0;i<h;i +=3)
for (j=0;j<w;j+=3)
{
char c; cin>>c;
if (c=='\\') a[j]=a[i+1][j+1]=a[i+2][j+2]=true;
else if (c=='/') a[j+2]=a[i+1][j+1]=a[i+2][j]=true;

}
(Where true means an obstacle, and false means free area)
This way, you have converted the maze:
/\/\/\
\\/\//
//\/\\
\/\/\/
Into the array (Black means true/obstacle):
......██............██............██......
...█......█......█......█......█......█...
█............██............██............█
█......█............██............█......█
...█......█......█......█......█......█...
......█......██............██......█......
......█......██............██......█......
...█......█......█......█......█......█...
█......█............██............█......█
█............██............██............█
...█......█......█......█......█......█...
......██............██............██......
Now you can simply do flood filling (up-down-left-right NO DIAGONALS), and count the number of cycles. You'll just have to divide each cycle length by 3 to get the true value for its length (remember your matrix is scaled by 3).

[sclo]

I found that it is cleaner to scale the board by 2 instead. The parity of the position tells you whether it is a valid square or not, then just construct adjacency matrix from there.

[seulkiro]

Man.. I had a stupid mistake. I was printing ":" after k Cycles instead of ';'. I was somehow getting wrong answer rather than presentation error. I guess it's because of the lack of a blank line after the last case. When I changed ':' to ';' in my output, I got presentation error. And putting a blank line after the last case solved the problem.

Make sure you put a blank line after each case. And don't confuse ';' with ':' like I did. heh

[ferrizzi]

I represent the maze using 3x3 divisions for each slash mentioned above. But I got stuck in how to get the cicles. In order to find the cycles, I do the following:

Code: Select all

maxLength=-1;
for(i=0; i<3*h; i++)
   for(j=0; j<3*w; j++){
       floodfill(i, j);
       if(foundACycle==true){
           ans++;
           if(cycleLength>maxLength) maxLength = cycleLength;
       }
   }

In my floodfill algorithm, I consider that I found a cycle when:
1. The square that I will visit next is visited AND
2. it is not my parent AND
3. it has the initial position i and j (global variables)

Could anyone help me?

Thank you![/code]

[ferrizzi]

The tests posted by jaywinyeah:

Code: Select all

0 1

1 0

aren't tested by the judge. The problem statement says that w, h are in the range [1, 75].

[ferrizzi]

I got AC today, but with 8.889 seconds. I guess this would get TLE in competition, is that right?

To find a cycle, I do the following:

1. I flood fill the region beginning at some position and count the numbers of squares = numberOfElements;
2. I flood fill again, but this time I check if next square (up, down, left and right) isn't my parent and if it is the initial position and cycleLength==numberOfElements. If this condition is true, then I found a Cycle. So I divide cycleLength by 3.

[rulio]

I am getting WA for this one, and i am stuck with it.
My code passes successfully the sample imputs given in this post, it handles any kind of 'wrong' maze declaration (I think),but I can' get rid of this WA...

Could anyone send some other sample inputs?

-------------
1231zg
abc45 32cvf
1 2 3
6 6
///\\\
///\\\
///\\\
\\\///
\\\///
\\\///

00
75 75
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
0 00
==>
Maze #1:
3 Cycles; the longest has length 20.

Maze #2:
2701 Cycles; the longest has length 4.

====

[jenovano2sko]

You know, I see a lot of people making crazy modifications for "flood fill" algorithms. Another easy way to do this problem is union find. AC in 0.012 seconds .

Pro tip: in general, the longest path between two vertices of a graph is NP-Complete. What properties of this graph make it so the longest path between a vertex and itself, if such a path exists, isn't NP-complete?

[panthenia]

plz endure my poor english
I hold that the biggest puzzle of this problem is how to build a map form the input to a graph,then we can use DFS to solve it.
we can build a matrix 2*mx2*n,every four rect describe a character '\'or'/',then its very easy to program.
I sole it in 0.020s.

[DD]

The tricky part of solving this problem is building a graph which transforms the input data into a x-y-aligned 2D array representation. After that, it just DFS to count the number of cycles and the maximum length of cycle.