705  Slash Maze
Moderator: Board moderators

 New poster
 Posts: 19
 Joined: Sun Aug 17, 2003 10:40 pm
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 (upperleft 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.
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 (upperleft 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.
LL Cool Jay
The Formula Wizard
Jason Winokur
The Formula Wizard
Jason Winokur

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
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 (updownleftright 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).
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 (updownleftright 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).
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
Make sure you put a blank line after each case. And don't confuse ';' with ':' like I did. heh
waikiki..
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:
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]
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;
}
}
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]
Regards,
[]'s
Andre
[]'s
Andre
The tests posted by jaywinyeah:
aren't tested by the judge. The problem statement says that w, h are in the range [1, 75].
Code: Select all
0 1
1 0
Regards,
[]'s
Andre
[]'s
Andre
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.
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.
Regards,
[]'s
Andre
[]'s
Andre
Re: 705  Slash Maze
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.
====
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.
====

 New poster
 Posts: 5
 Joined: Tue Oct 19, 2010 8:07 am
Re: 705  Slash Maze
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 NPComplete. What properties of this graph make it so the longest path between a vertex and itself, if such a path exists, isn't NPcomplete?
Pro tip: in general, the longest path between two vertices of a graph is NPComplete. What properties of this graph make it so the longest path between a vertex and itself, if such a path exists, isn't NPcomplete?
Re: 705  Slash Maze
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.
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.

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 705  Slash Maze
The tricky part of solving this problem is building a graph which transforms the input data into a xyaligned 2D array representation. After that, it just DFS to count the number of cycles and the maximum length of cycle.
Have you ever...
 Wanted to work at best companies?
 Struggled with interview problems that could be solved in 15 minutes?
 Wished you could study realworld problems?