OJ Board

I also tried BFS,but still tle. Anything else I should do?

One thing for sure is that it will take less than 11 moves to move from a square to any of the other.

Therefore prime moves are limited to 2, 3, 5, and 7.

I used IDS.

sohel wrote: I used IDS.

Do you use 2,3,5,7 as the threshold and simplily do IDS?

I' got AC ;following is my approach:

First,use BFS to know whether there is a path from source to destination.If it exists,record the length,and if it is prime,then that is the result,otherwise it is the min composite number,in this case, we shall goto IDS procedure.

Then,I use IDS to search the prime length path,if it exists, that's ok;otherwise,print the min composite number,we got in the BFS.

Hope it will help the new coming acmers trying to solve this problem.

Congrats Wiltord,
That's exactly what i have done.

I think the problem is very simple.
I used simple BFS with some condition to solve the problem .

I think the problem involves with negetive input & then we have to avoid it. Thanks

I think the problem is very simple.
I used simple BFS with some condition to solve the problem .

I think the problem involves with negetive input & then we have to avoid it. Thanks

sohel wrote:One thing for sure is that it will take less than 11 moves to move from a square to any of the other.

Therefore prime moves are limited to 2, 3, 5, and 7.

Hi. I was suffering from TLEs and got to here, and saw your post and immediately got AC. But I'm still curious How do you know you can never reach destination with prime cost larger than 7?

Thanks in advance,
JongMan

I actually figured it out by trial and error.

Consider this:
the maximum number of moves required is to go from the top-left square
to bottom right. ie
from (0, 0) to (14,14).

The minimum number of moves required for this is less than 11. So it is obvious that to go from one square to any other it will definitely require less than 11 moves. So if you can't reach a square in ten moves then you will never be able to reach it.


Therefore 7 moves should be enough if a path is possible.
Hope it helps.

Hi Sohel,

Could you give more explanation on the proof?
I wonder if there is a case that, the destination has composite shortest distance from start point but it also has a prime move > 7, because the chess can first walk to other place of the board to "waste" some step first.......

Do you have any proof that there is no such case???
Thanks!

aztec knight moves are (+/- 1, +/-3) or (+/- 3, +/- 1), so all moves are (+odd,+odd). A parity argument will convince you that if it's possible to get from one point to another in an even number of moves, it must be impossible in an odd number of moves - and vice versa.

Yes, but how about if the shortes distance between 2 squares is 1?
There will not be even length path between 2 squares, but your argument can't exclude the existance of path with length 11(or any larger odd prime).

oh doh...i completely forgot that odd numbers can also be composite i think i am losing my mind

Edit:

I will make a claim that I think can be proven by case-by-case analysis, but I'll think about proving it later: if you can get from one square to another in 1 step, then you can either also get there in 3 steps or else you can't get there at all in >=3 steps. in other words for example, it's impossible to get to be able to get to a place 1 move away in 5 steps while not being able to do it in 3.

i think proving the claim may not be so hard actually..to do it in 3 you need either a 7x3 or 5x5 rectangle's worth of space enclosing the point you're at and the point you're trying to get to. to do it in > 3, you'd need even more space.

so if this claim is true and you think my semi-proof makes sense, combine it with the fact that all odd numbers from 3-7 are prime and that no distance is ever over 10 (actually i think never over 8, but definitely not 10) to prove what sohel said.

What I realized was that you can not reach (14, 14) from (0, 0) in 11 moves. So I came to the conclusion that there does not exist any path that has a length of 11.

.. wrote: I wonder if there is a case that, the destination has composite shortest distance from start point but it also has a prime move > 7, because the chess can first walk to other place of the board to "waste" some step first.......

I don't think you can reach a place in more than 7 prime moves even if you waste some steps by fooling around about the board.

I don't have any mathematical or logical proof for this but I think it is correct, despite that think is a very weak word in programming.

hm, actually, if you can show that the *shortest path* from any
square to any other square is < 9, i think my reasoning above works.
the shortest path from 0,0 to any other square is 8, but i haven't checked
from other spots.

in case my reasoning wasn't clear..

if the shortest path is <9 the only odd options for path lengths
are 1,3,5,7. 3,5,7 are prime so it:s ok. The only question is whether
we can 'fool around' and do it in a prime # of moves > 1 when the
shortest distance is 1.

in order for us to get somewhere in 3 moves such that there is also a 1-move-path to, we need at least either a 5x5 or 7x3 rectangle enclosing us and the point we're going to. To get somewhere in more than 3 moves, we're told that the path is not allowed to touch the same square twice
so the rectangle size we need only gets larger. this implies that if we can get somewhere in 1 move, we can either also get there in 3 or can't get there for any n>=3.