Welcome, guest! Login / Register - Why register?
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

Your Name: Code Language: