10463 - Aztec Knights

ras46 · Post by **ras46** » Thu Mar 06, 2003 1:37 pm

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

kmhasan · Post by **kmhasan** » Thu Mar 06, 2003 6:50 pm

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?

ras46 · Post by **ras46** » Fri Mar 07, 2003 2:53 am

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?

ras46 · Post by **ras46** » Fri Mar 07, 2003 5:50 am

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

Caesum · Post by **Caesum** » Fri Oct 31, 2003 8:30 pm

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 ?

kmhasan · Post by **kmhasan** » Fri Oct 31, 2003 9:40 pm

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).

Caesum · Post by **Caesum** » Sat Nov 01, 2003 2:02 am

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

Dmytro Chernysh · Post by **Dmytro Chernysh** » Sat Nov 01, 2003 2:04 am

The same problem Caesum...

kmhasan · Post by **kmhasan** » Sat Nov 01, 2003 5:05 am

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.

wiltord · Post by **wiltord** » Mon Dec 01, 2003 6:21 am

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

sohel · Post by **sohel** » Mon Dec 01, 2003 8:51 am

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.

wiltord · Post by **wiltord** » Mon Dec 01, 2003 11:25 am

I have found the way now,it is really i misunderstood the move rules.thank you!

[/quote][/cpp]

wiltord · Post by **wiltord** » Mon Dec 01, 2003 4:20 pm

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!

wiltord · Post by **wiltord** » Tue Dec 02, 2003 4:12 pm

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

Larry · Post by **Larry** » Wed Dec 03, 2003 8:12 am

BFS should be enough..

OJ Board

10463 - Aztec Knights

10463 - Aztec Knights

10463 Aztec knights

10463 Aztec knights how to avoid tle