online-judge.uva.es

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

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

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?

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?

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

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

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 ?

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

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

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

The same problem Caesum...

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.

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

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. :wink:

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]

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!

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.

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

BFS should be enough..

online-judge.uva.es

10463 - Aztec Knights

10463 - Aztec Knights

10463 Aztec knights

10463 Aztec knights how to avoid tle

Who is online