10952 - Pattern Transformations

[CrazyTerabyte]

hey, wait! The sample output says the first pattern requires 0 swaps, but the problem description says it requires 1 swap... Something is very wrong here.

[mf]

It's a mistake. Zero swaps is the correct answer.

[CrazyTerabyte]

One more question: In this problem, we must discover if we can transform the first pattern into second one in *one* step, right? So: X.. and ..X would answer -1. Is this right?

[mf]

That's right.

[shanto86]

My brute force code and bitmap code both getting tle i can't understand why!

any idea:

Code: Select all

REMOVED

[shanto86]

Well... now i need help. I am getting WA. can you please give me some sample input output?

PS: (I had some mistake in the code. so i fixed and avoided TLE. it is giving WA in 2sec.)

[mf]

Here are some tests:

Code: Select all

13

3 4
.X. .X.
.OX XO.
..O .O.
... ...

2 3
XO OX
.. .X
OX XO

2 4
XO OX
.. .X
OX XO
.. ..

4 4
OXOX XOXO
XOXO OOXX
OXOX XOXO
XOXO OXOX

2 2
OO XO
XO OO

5 3
.XO.. ..XO.
..OX. .XX..
.XX.. ..OX.

4 4
OXOX XOXO
XX.O OX.X
O..X X..O
XOXO OXOX

4 5
.... ....
.XO. .OX.
.X.. ..X.
.OX. .XO.
.... ....

4 4
XXOX O.XO
O.OO XXOX
OX.X .XXO
XOXX OXOX

8 8
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO OXOXOXOX

8 8
XOXOXOXO XOOXOXOX
XOXOXOXO OXOXXOOX
XOXOXOXO OXXOOXOX
XOXOXOXO OXOXOXOX
XOXOXOXO XOOXOXOX
XOXOOXXO OXOXOXOX
XOXOXOXO OXXOOXOX
XOXOXOXO OXOXOXOX

8 8
XOXOXOXO .XOXOXOO
XOXOXOXO XXOXOXOO
XOXOXOXO XOXXOOXO
XOXOXOXO XXOOXXOO
XOXOXOXO OXOXXXOO
XOXOXOXO XXOOXOXO
XOXOXOXO XOXXOOXX
XOXOXOX. XXOOXXOO 

8 8
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX
XOXOXOXO OOOOOOOO
XOXOXOXO XXXXXXXX

Code: Select all

-1
-1
-1
0
0
0
0
1
3
32
26
9
0

[shanto86]

got AC. thanks!

Poor timing using bitset of stl!