輸油管道 (Standard IO)

題意/Description:

       請你幫忙設計一個從城市M到城市Z的輸油管道，現在已經把整個區域劃分為R行C列，每個單元格可能是空的也可能是以下7種基本管道之一：

       油從城市M流向Z，‘+’型管道比較特殊，因為石油必須在兩個方向（垂直和水準）上傳輸，如下圖所示：

       現在恐怖分子弄到了輸油管道的設計圖，并把其中一個單元格中的管道偷走了，請你幫忙找到偷走的管道的位置以及形狀。

讀入/Input：

       第一行包含兩個整數R和C（1<=R,C<=25）。

　　接下來R行每行C個字元描述被偷之後的形狀，字元分為以下三種：

　　(1)‘.’表示空；

　　(2)字元‘|’（ASCII為124）、‘-’、‘+’、‘1’、‘2’、‘3’、‘4’描述管道的形狀；

　　(3)‘M’和‘Z’表示城市，兩個都是隻出現一次。

　　輸入保證石油的流向是唯一的，隻有一個管道跟M和Z相連，除此此外，保證沒有多餘的管道，也就是說所有的管道在加進被偷的管道後一定都會被用上。

　　輸入保證有解而且是唯一的。

輸出/Output：

       輸出被偷走的管道的行号和列号以及管道的類型。

題解/solution：

       首先題目告訴我們恐怖分子隻偷走了一個管道。我們從M點或Z點出發，順這管道出發，找到那個漏油的地方（管道被偷之前肯定不會漏油），就是被偷走的管道的行号和列号。怎麼判斷呢？如果是‘-’，那必須和左右聯通，不能和上下聯通（很顯然）；如果是‘|’，那必須和上下聯通，不能和左右聯通（也很顯然）；‘+’，必須和上下左右聯通（十分顯然）。1、2、3、4也一樣了，聽完後，是不是水啊！

       點個贊啊，有不足告訴我。

代碼/Code：

var
  n,m,x1,x2,y1,y2,o,p:longint;
  a:array [0..30,0..30] of char;
  f:array [0..30,0..30] of boolean;
  dx,dy:array [1..4] of integer;
procedure init;
var
  i,j:longint;
begin
  fillchar(f,sizeof(f),0);
  readln(n,m);
  for i:=1 to n do
    begin
      for j:=1 to m do
        begin
          read(a[i,j]);
          if a[i,j]='M' then
            begin
              x1:=i; y1:=j;
            end;
          if a[i,j]='Z' then
            begin
              x2:=i; y2:=j;
            end;
        end;
      readln;
    end;
end;

function fd(x,y:longint):boolean;
begin
  if (x<0) or (x>n+1) or (y<0) or (y>m+1) then exit(true);
  exit(false);
end;

procedure main(x,y:longint);
var
  i:longint;
begin
  if fd(x,y) or (f[x,y]) then exit;
  f[x,y]:=true;
  if a[x,y]='.' then
    begin
      o:=x; p:=y;
      exit;
    end;
  if a[x,y]='M' then
    begin
      for i:=1 to 4 do
        if a[x+dx[i],y+dy[i]]<>'.' then main(x+dx[i],y+dy[i]);
    end else
    case a[x,y] of
      '|':if f[x+dx[1],y+dy[1]] then main(x+dx[3],y+dy[3])
                                else main(x+dx[1],y+dy[1]);
      '-':if f[x+dx[2],y+dy[2]] then main(x+dx[4],y+dy[4])
                                else main(x+dx[2],y+dy[2]);
      '+':for i:=1 to 4 do main(x+dx[i],y+dy[i]);
      '1':if f[x+dx[3],y+dy[3]] then main(x+dx[4],y+dy[4])
                                else main(x+dx[3],y+dy[3]);
      '2':if f[x+dx[1],y+dy[1]] then main(x+dx[4],y+dy[4])
                                else main(x+dx[1],y+dy[1]);
      '3':if f[x+dx[1],y+dy[1]] then main(x+dx[2],y+dy[2])
                                else main(x+dx[1],y+dy[1]);
      '4':if f[x+dx[3],y+dy[3]] then main(x+dx[2],y+dy[2])
                                else main(x+dx[3],y+dy[3]);
    end;
end;

function t1(x,y:longint):boolean;
begin
  if a[x,y]='1' then exit(true);
  exit(false);
end;

function t2(x,y:longint):boolean;
begin
  if a[x,y]='2' then exit(true);
  exit(false);
end;

function t3(x,y:longint):boolean;
begin
  if a[x,y]='3' then exit(true);
  exit(false);
end;

function t4(x,y:longint):boolean;
begin
  if a[x,y]='4' then exit(true);
  exit(false);
end;

function t5(x,y:longint):boolean;
begin
  if a[x,y]='+' then exit(true);
  exit(false);
end;

function t6(x,y:longint):boolean;
begin
  if a[x,y]='-' then exit(true);
  exit(false);
end;

function t7(x,y:longint):boolean;
begin
  if a[x,y]='|' then exit(true);
  exit(false);
end;

procedure print;
var
  x,y:array [1..4] of longint;
  f1,f2,f3,f4:boolean;
  i:longint;
begin
  if (o=0) and (p=0) then
    begin
      if fd(x1-2,y1) and (a[x1-2,y1]<>'.') then begin o:=x1-2; p:=y1; end else
        if fd(x1+2,y1) and (a[x1+2,y1]<>'.') then begin o:=x1+2; p:=y1; end else
          if fd(x1,y1-2) and (a[x1,y1-2]<>'.') then begin o:=x1; p:=y1-2; end else
            if fd(x1,y1+2) then begin o:=x1; p:=y1+2; end;
    end;
  write(o,' ',p,' ');
  for i:=1 to 4 do
    begin
      x[i]:=o+dx[i]; y[i]:=p+dy[i];
    end;
  f1:=t2(x[2],y[2]) or t1(x[2],y[2]) or t5(x[2],y[2]) or t6(x[2],y[2]);
  f2:=t3(x[4],y[4]) or t4(x[4],y[4]) or t5(x[4],y[4]) or t6(x[4],y[4]);
  f3:=t4(x[1],y[1]) or t1(x[1],y[1]) or t5(x[1],y[1]) or t7(x[1],y[1]);
  f4:=t2(x[3],y[3]) or t3(x[3],y[3]) or t5(x[3],y[3]) or t7(x[3],y[3]);
  if (not f1) and (not f2) and (f3) and (f4) then write('|');
  if (f1) and (f2) and (not f3) and (not f4) then write('-');
  if (f1) and (f2) and (f3) and (f4) then write('+');
  if (not f1) and (f2) and (not f3) and (f4) then write('1');
  if (not f1) and (f2) and (f3) and (not f4) then write('2');
  if (f1) and (not f2) and (f3) and (not f4) then write('3');
  if (f1) and (not f2) and (not f3) and (f4) then write('4');
end;

begin
  init;
  dx[1]:=-1; dx[2]:=0; dx[3]:=1; dx[4]:=0;
  dy[1]:=0; dy[2]:=-1; dy[3]:=0; dy[4]:=1;
  main(x1,y1);
  print;
end.