麻将游戏
Description
在一種”麻將”游戲中，游戲是在一個有W＊H格子的矩形平板上進行的。每個格子可以放置一個麻將牌，也可以不放（如圖所示）。玩家的目標是將平板上的所有可通過一條路徑相連的兩張相同的麻將牌，從平板上移去。最后如果能將所有牌移出平板，則算過關。
這個游戲中的一個關鍵問題是：兩張牌之間是否可以被一條路徑所連接，該路徑滿足以下兩個特性：
1. 它由若干條線段組成，每條線段要么是水平方向，要么是垂直方向。
2. 這條路徑不能橫穿任何一個麻將牌 (但允許路徑暫時離開平板)。
這是一個例子：
在（1，3）的牌和在(4, 4)的牌可以被連接。(2, 3)和(3, 4)不能被連接。
你的任務是編一個程序，檢測兩張牌是否能被一條符合以上規定的路徑所連接。
Input
輸入文件的第一行有兩個整數w，h （1<=w，h<=75），表示平板的寬和高。接下來h行描述平板信息，每行包含w個字符，如果某格子有一張牌，則這個格子上有個’X’，否則是一個空格。平板上最左上角格子的坐標為（1，1），最右下角格子的坐標為（w,h）。接下來的若干行，每行有四個數x1， y1， x2， y2 ，且滿足1<=x1,x2<=w，1<=y1,y2<=h，表示兩張牌的坐標（這兩張牌的坐標總是不同的）。如果出現連續四個0，則表示輸入結束。
Output
輸出文件中，對于每一對牌輸出占一行，為連接這一對牌的路徑最少包含的線段數。如果不存在路徑則輸出0。
Sample Input
5 4
XXXXX
X X
XXX X
XXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
Sample Output
4
3
0
分析
用廣搜來做
每一次向四個方向搜（上、下、左、右）一直搜到有麻將擋住為止。（ps：麻將的路線可以走到棋盤外面）
程序：
const dx:array[1..4]of longint=(0,1,0,-1); dy:array[1..4]of longint=(1,0,-1,0);var i,j,head,tail,n,m,qx,qy,px,py:longint; state:array[-1..10000,1..2]of longint; father:array[-1..100,-1..100]of longint; f:array[-1..10000]of integer; a:array[-1..100,-1..100]of char; bz:boolean;function pd(x,y:longint):boolean; beginpd:=not(true);if (x>m+1)or(x<0)or(y>n+1)or(y<0) then exit;if a[x,y]='X' then exit;if f[head]+1<=f[father[x,y]] then pd:=true; end;procedure try(x,y:longint); begininc(tail);state[tail,1]:=dx[x]*y+state[head,1];state[tail,2]:=dy[x]*y+state[head,2];father[state[tail,1],state[tail,2]]:=tail;f[tail]:=f[head]+1;if (state[tail,1]=qx)and(state[tail,2]=qy) thenbeginwriteln(f[tail]);head:=0;exit;end;if not(pd(state[tail,1]+dx[x],state[tail,2]+dy[x])) then exit;try(x,y+1); end;procedure bfs; var i:longint; beginhead:=0; tail:=1;state[1,1]:=px; state[1,2]:=py; f[1]:=0; father[px,py]:=1;repeatinc(head);for i:=1 to 4 doif pd(state[head,1]+dx[i],state[head,2]+dy[i]) thenbegintry(i,1);if head=0 then exit;end;until head>=tail;writeln(0); end;beginreadln(n,m);for i:=1 to m dobeginfor j:=1 to n doread(a[i,j]);readln;end;bz:=true;while bz=true dobeginfillchar(f,sizeof(f),$7f div 2);readln(py,px,qy,qx);if (px=0)and(0=py)and(0=qx)and(0=qy) then break;a[qx,qy]:=' ';bfs;a[qx,qy]:='X';fillchar(state,sizeof(state),#0);fillchar(father,sizeof(father),#0);end; end.轉載于:https://www.cnblogs.com/YYC-0304/p/9500057.html
總結
