Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)
Paste
Pasted as Delphi by Fyodor ( 13 years ago )
program KingsExchangePositions;
{$APPTYPE CONSOLE}
uses
SysUtils, Math;
type
Integer = LongInt;
Real = Extended;
const
MAX_HEIGHT = 10;
MAX_WIDTH = 10;
MAX_STATES = MAX_HEIGHT * MAX_WIDTH * 2;
INFINITY = 10 * MAX_STATES;
function Encode(rw, cw, rb, cb, turn, height, width : Integer) : Integer;
var
x1, x2, y, res : Integer;
begin
Dec(rw); // нумеруем с нуля
Dec(rb);
Dec(cw);
Dec(cb);
Dec(turn);
x1 := rw * width + cw;
x2 := rb * width + cb;
y := x1 * (height * width) + x2;
res := 2 * y + turn;
Encode := res;
end;
procedure Decode(code : Integer; var rw, cw, rb, cb, turn : Integer; height, width : Integer);
var
x1, x2 : Integer;
begin
turn := code mod 2;
code := code div 2;
x1 := code div (height * width);
x2 := code mod (height * width);
rw := x1 div width;
cw := x1 mod width;
rb := x2 div width;
cb := x2 mod width;
Inc(rw);
Inc(cw);
Inc(rb);
Inc(cb);
Inc(turn);
end;
var
height, width, r, c, rw, cw, rb, cb, i, qt, qh, res : Integer;
start, finish1, finish2, u, v, turn, dr, dc, nr, nc, er, ec : Integer;
board : Array[0..MAX_HEIGHT] of String;
q, distance : Array[0..MAX_STATES] of Integer;
begin
Assign(input, 'input.txt');
Reset(input);
Assign(output, 'output.txt');
Rewrite(output);
ReadLn(height, width);
for r := 1 to height do begin
ReadLn(board[r]);
end;
for r := 1 to height do begin
for c := 1 to width do begin
if board[r][c] = 'W' then begin
rw := r;
cw := c;
end;
if board[r][c] = 'B' then begin
rb := r;
cb := c;
end;
end;
end;
start := Encode(rw, cw, rb, cb, 1, height, width);
finish1 := Encode(rb, cb, rw, cw, 1, height, width);
finish2 := Encode(rb, cb, rw, cw, 2, height, width);
for i := 0 to MAX_STATES do
distance[i] := INFINITY;
distance[start] := 0;
qt := 1;
qh := 2;
q[1] := start;
while qt < qh do begin
v := q[qt];
Inc(qt);
Decode(v, rw, cw, rb, cb, turn, height, width);
if turn = 1 then begin
r := rw;
c := cw;
er := rb; // enemy
ec := cb;
end else begin
r := rb;
c := cb;
er := rw;
ec := cw;
end;
for dr := -1 to 1 do begin
for dc := -1 to 1 do begin
if (dr = 0) and (dc = 0) then continue;
nr := r + dr;
nc := c + dc;
if (nr < 1) or (nr > height) then continue;
if (nc < 1) or (nc > width) then continue;
if board[nr][nc] = '*' then continue;
if Max(Abs(nr - er), Abs(nc - ec)) <= 1 then continue;
if turn = 1 then begin
// turn' = 3 - turn
u := Encode(nr, nc, rb, cb, 2, height, width);
end else begin
u := Encode(rw, cw, nr, nc, 1, height, width);
end;
if distance[u] > 1 + distance[v] then begin
distance[u] := 1 + distance[v];
q[qh] := u;
Inc(qh);
end;
end;
end;
end;
res := Min(distance[finish1], distance[finish2]);
if res = Infinity then
WriteLn('Impossible')
else
WriteLn(res);
end.
Revise this Paste