OJ Board

My thought is backtracking. But it's too inefficent.
Try to find all possible solutions.
But it looks like a nim game, should have a faster method
Could someone give me some hints,thx:)

Memorization. Don't call dfs again if the current state is known because one state will always have only one possible answer.

the correct term is MEMOIZATION, not memorization.
it's a form of Dynamic Programming (top-down instead of bottom-up).

Sorry, I used memoization at first (p10157 related post). But I saw somebody use the word "memorization". It indeed confused me.

LittleJohn wrote:Sorry, I used memoization at first (p10157 related post). But I saw somebody use the word "memorization". It indeed confused me.

Sorry, What's the output for the input
10

....
....
....
....

.X..
..X.
XX..
...X

...X
.X..
X..X
..XX

X..X
....
....
X..X

....
.XX.
.XX.
....

XXXX
X..X
X..X
X...

.XX.
X..X
X..X
.XX.

..XX
XX..
...X
X...

....
X..X
.X..
...X

XXXX
....
..X.
XXX.

Thx in advance

my AC program gives Good Luck

LittleJohn wrote:my AC program gives

Code: Select all

LOSING
WINNING
WINNING
WINNING
LOSING
WINNING
WINNING
LOSING
LOSING
LOSING

Good Luck

Hi LittleJohn, could you tell me how your program took the first step in
the last test case? My program took the first step as follows
XXXX
. XX .
. . X .
XXX .
I really don't know why it will lose.

Hi sharklu,
It's the only trick in this problem.
Something wrong(illegal) with your first step,
just read the problem description and take a look at the picture again.
think about it.

thank you John, I got ac now.

Hello,I have just passed this problem with a very
long(>140 lines) and slow (>0.8sec) program.
Would anyone with a faster solution like to exchange
codes with me?I'd like to make an improvement.
Mail me.Thanks in advance.

I use 2^16 to model the board and using minimax algorithm to solve it.. but i got WA...
Did it has special case?