I used a little different approach from the one mentioned on this board. It was based on weighted quick-union described by Sedgewick... I made a stupid logical mistake which caused my program to work the longest time possible, so first I got TLE#10 (solutionID=861144). Then I optimized my code with path compression (see Sedgewick once again) and got AC in 0.125 sec (solutionID=861147). Then I realized my error, removed path compression and got AC in 0.078 s (solutionID=861151). Adding path compression back slowed my solution a bit (0.109 s, solutionID=861153). All my solutions consume 449 KB of memory.

I'm interested in time and memory requirements of other possible algorithms. I haven't got their implementations, so I cann't submit them myself.

If somebody feels interested about my approach to this problem, just let me know - I'll explain.

Hello,

I tried to create a graph for this problem in this way:
Vertices correspond to intersections of the board (left upper (0; 0) and right lower (n; m)).
I will denote the vertice by [i][j][l]. If i = 0, then we have face of the cloath, else if i = 1, we have the rear of the cloth. j means the row, and l - column.

For the example test, graph edges:
[0][1][1] <-> [1][2][2]
[0][2][2] <-> [1][1][1]
[0][2][2] <-> [1][3][3]
[0][3][3] <-> [1][2][2]
[1][2][1] <-> [0][3][2]
[1][2][2] <-> [0][3][3]
[1][2][3] <-> [0][3][2]
[1][2][5] <-> [0][1][4]
[1][3][2] <-> [0][2][1]
[1][3][2] <-> [0][2][3]
[1][3][3] <-> [0][2][2]

I can not count degrees correctly with this graph even for the example test. Is there a better graph representation? If no, how to solve the problem with this one?

I was completely mad of it!
 (By the way ,my English is poor.)

I cant understand problem statement , I'm reading it for 1 hour and can't understand what they want ;( please explain it to me...
thanks

As far as I can see the problem has relatively small
percent of the difficulty, but I can't think of the way I
should walk the pattern by means of minimal number of
threads..

Is the problem only a DFS (and if it is how should it be
done) or there is something else?

Thank you.

give you some test~~
5 4
..\/
\/..
/X..
..X/
..X.
..X.
\/\/
\/..
\/..
\/..
ans:13
3 3
..\
/\X
...
..\
///
...
ans:2

Who can help me?


my email address:yby.barty@163.com

What's the answer of this input, why?
2 2
\/
/\
\/
/\
I think it should be 2.

Edited by author 04.08.2006 11:09

I got WA#9.
Does any one know anything about #9. Or can any one offer me some tests?
3Q.

It is said in the input "...The symbols used are “.”, “/”, “” and “X”...". Looks like it should be "\" instead of "". Am I right? Or it is necessary to check every possible position of "\" character?

Is the algorithm that DFS all the vertices and count the number of threads?
But why wrong answer on test#9?
Is there any tricky input available?