OJ Board

I got wa many times ..
Is there any tricky input ?

it may happen that you can reach the destination in 1 move (which is composite) but you can reach it in 3 moves (which is prime).
does your solution handle those cases?

Hi,kmhasan.
I have handled this case , but still WA.

5 5 0 0 1 3
CASE# 1: The knight takes 3 prime moves.

Is my output correct?

I found a mistake in my sourcecode.
I got AC after correcting it ..

Am I right in saying that a knight at (0,0) can move to (3,1) but that a knight at (3,1) cannot move to (0,0) since one of the intermediate moves would be off the board ?

No. I think if a knight can go from (0,0) to (3,1) then it can also go from (3,1) to (0,0).

any ideas for avoiding a tle on this ? at the moment i pretty much do brute force with some heuristics but it is slow........

The same problem Caesum...

Spoiler follows:

I run a IDS (Iterative Deepening Search) keeping track of the cells I visit while searching within a certain depth. If this track is kept, then we are not going to explore the cells in that depth again if it leads to unsuccessful searches.

A preprocessing with BFS can make the solution run even faster. In that case we can use the prime numbers as the depth of IDS.

how to understand the second data set in the sample. i can't find a two steps move from (0,0) to (4,4).

Hi Wiltord,

Perhaphs you misunderstood the question.
Aztecs Knights are special: they move three spaces horizontally/vertically and one space vertically/horizontally.

So (0,0) to (4,4):

(0,0) to (3,1) - 1st move.
(3,1) to (4,4) - 2nd move.

Hope it helps.

I have found the way now,it is really i misunderstood the move rules.thank you! [/quote][/cpp]

I run a IDS (Iterative Deepening Search) keeping track of the cells I visit while searching within a certain depth. If this track is kept, then we are not going to explore the cells in that depth again if it leads to unsuccessful searches

please tell me more specificly,how to do with the keeping track of the cells and not going to explore the cells int that depth again! thank you!

who can help me? I can't really find an effective way to avoid tle. thanks before.

BFS should be enough..