## 10463 - Aztec Knights

Moderator: Board moderators

### 10463 - Aztec Knights

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

Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan

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?

kmhasan
Problemsetter

Posts: 107
Joined: Fri Oct 26, 2001 2:00 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
New poster

Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan

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

Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan

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 ?
Caesum
Experienced poster

Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK

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

kmhasan
Problemsetter

Posts: 107
Joined: Fri Oct 26, 2001 2:00 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........
Caesum
Experienced poster

Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK

The same problem Caesum...
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 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.

kmhasan
Problemsetter

Posts: 107
Joined: Fri Oct 26, 2001 2:00 am

### 10463 Aztec knights

how to understand the second data set in the sample. i can't find a two steps move from (0,0) to (4,4).
my goal: master algorithms
wiltord
New poster

Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

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.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

I have found the way now,it is really i misunderstood the move rules.thank you! [/quote][/cpp]
my goal: master algorithms
wiltord
New poster

Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

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!
my goal: master algorithms
wiltord
New poster

Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

### 10463 Aztec knights how to avoid tle

who can help me? I can't really find an effective way to avoid tle. thanks before.
my goal: master algorithms
wiltord
New poster

Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

BFS should be enough..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Next