10477 - The Hybrid Knight

[sqrt3lj]

const
mv: array[0..2, 1..8, 1..2]of longint =
(
((-2, -1), (-2, 1), (-1, 2), (1, 2),
(2, 1), (2, -1), (1, -2), (-1, -2)),

((-3, -1), (-3, 1), (-1, 3), (1, 3),
(3, 1), (3, -1), (1, -3), (-1, -3)),

((-1, 0), (1, 0), (0, -1), (0, 1),
(-1, -1), (-1, 1), (1, -1), (1, 1))
);
err = $7fffffff;

type
TMap = array[0..20 * 20 - 1, 0..2]of longint;

var
n: longint;
q: array[1..20 * 20 * 3 + 2, 1..2]of longint;
h, t: longint;

procedure travel(x0, y0: longint; var map: TMap);
var
i, j, k: longint;
begin
for i := 0 to n * n - 1 do
for k := 0 to 2 do
map[i, k] := err;
for k := 0 to 2 do
begin
map[x0 * n + y0, k] := 0;
q[k + 1, 1] := x0 * n + y0;
q[k + 1, 2] := k;
end;
h := 1; t := 3;
repeat
x0 := q[h, 1] div n;
y0 := q[h, 1] mod n;
for k := 1 to 8 do
begin
i := x0 + mv[q[h, 2], k, 1];
j := y0 + mv[q[h, 2], k, 2];
if(i < 0)or(i >= n)or(j < 0)or(j >= n)then continue;

i := i * n + j;
j := (q[h, 2] + 1) mod 3;

if map[i, j] < err then continue;

map[i, j] := map[q[h, 1], q[h, 2]] + 1;
inc(t);
q[t, 1] := i;
q[t, 2] := j;
end;

inc(h);
until h > t;
end;

var
dist: array[0..20 * 20 - 1, 0..20 * 20 - 1]of longint;
map: TMap;

i, j, k, min: longint;
dataid: longint;
begin
dataid := 0;
repeat
read(n);
if n < 4 then break;
inc(dataid);
writeln('Set ', dataid, ':');

fillchar(dist, sizeof(dist), 0);
for i := 0 to n * n - 1 do
begin
travel(i div n, i mod n, map);
for j := 0 to n * n - 1 do
begin
min := err;
for k := 0 to 2 do
if map[j, k] < min then
min := map[j, k];
dist[i, j] := min;
end;
end;

read(k);
while k > 0 do
begin
read(i, j);
dec(i); dec(j);
if dist[i, j] < err then writeln(dist[i, j])
else writeln('?');
dec(k);
end;
until false;
end.

[little joey]

Try:

Code: Select all

20 1
1 10
0 1

Your answer: 4
Correct answer: 5

I'm not gonna look into your code. If you realy expect that anyone does, then don't make it too difficult for them:
- Use the formatting tags,
- Use descriptive names for your variables and put in some comment.

You're a Pascal programmer, not a C programmer, so there's no reason to make it hard on yourself and others!

[Harun (IIUC)]

Hello, i solve the problem 10477. but i got TLE.
Who can i overcome it.
May be my algorithm is Bad. Is their anybody who provide me a good algorithm ?

[Larry]

Breadth first search should work..

[Harun (IIUC)]

I use DFS for this 10477 problem. in my program i use DFS three(3) times. i think that causes TLE. But how can i use only one DFS call for this problem?

[kmhasan]

So far as I understand even one DFS per query would get TLE. I used BFS to get single source shortest path and filled up a table which contains all pair shortest path.

However, the coding was optimized by doing BFS from one fourth of the source vertices. We can use the symmetry of the board if we know the all single source shortest paths for one quadrant of a board.

Think about it.

[titid_gede]

hi...

i use BFS, but got WA. however what i'm confuse is in this statement :

However if the final move is made with the mutant pawn, the pawn has options to use its attacking move

here, what if the meaning of final move?
thanks before,

regards,
titid gede

[Dominik Michniewski]

If you send me PM with IO, I got the same results as you

Best regards
DM

[sohel]

I am also confused about 'the final move statement' .

Can the destination be reached with using the pawn's normal move ie
vertical and horizontal ones.

I used BFS and got WA in 1.410 seconds. I have tried with different cases and can't find the fault. Is there any critical input?

[Andrey Mokhov]

Hi!

As far as I remember, that foggy phrase means that the last move of the pawn may be either usual or attacking move. So you are just to check if you can attack the target by pawn you should attack. If you can't - just make usual move.

Have AC!
Andrey.

[sohel]

I considered everything mentioned but still WA.

Initially I enqued the source postion three times with the three different types. And at each deque I marked the adjacent nodes depending on the type dequed. And when destination is reached I printed that value.

Where is the mistake?
Thanx.

[titid_gede]

did you considered if last move by mutant pawn, that it has an option to use his attacking move?
gut lak!

[sohel]

Yes, I considered that too.

But for each query do you have to call bfs() three times or
(can you just call it once and initially enquing the queue with the three types.)

[sohel]

Just got AC.

I made a very stupid mistake.
For those who are still having difficulty: you can either call bfs() 3 times or have a 3 dimensional visited array.

[Andrey Mokhov]

Hi!

In my program I enqueued only one state but that was a special state - there were three possibilities to go from it to usual states.

By the way what if your program will be given a test where a pawn can use its attacking possibility on the first move? Did you handle this properly?

Good luck!
Andrey.