CODEVS 1004四子连棋

【题目描述 Description】

在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●	○	●
○	●	○	●
●	○	●	○
○	●	○

输入描述 Input Description

从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。

输出描述 Output Description

用最少的步数移动到目标棋局的步数。

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

【解题思路】

只能这样说，这是一个特别练DFS和BFS的题目，因为它的数据范围很小，怎么搜都不会超时，但是写深搜的孩子要注意，不能只从一个空格开始搜，而是在搜索完每一个节点之后都要进行一个双重循环寻找空格，因为空格有两个！有两个！

 1 program FourChess;
 2 const fx:array[1..4] of longint=(1,-1,0,0);
 3       fy:array[1..4] of longint=(0,0,1,-1);
 4 var
 5 f:array[1..4,1..4] of longint;
 6 i,j:longint;
 7 min:longint;
 8 ch:char;
 9 
10 
11 procedure dfs(x,y,num,co:longint);
12 var i,j,k,m,flag:longint;
13 begin
14     flag:=0;
15      if num>=min then exit;
16      for i:=1 to 4 do
17      begin
18         if (f[i,1]=f[i,2]) and(f[i,2]=f[i,3]) and(f[i,3]=f[i,4])and((f[i,4]=1) or(f[i,4]=2)) then
19         BEGIN
20             m:=num;
21             flag:=1;
22         end;
23         if (f[1,i]=f[2,i]) and(f[2,i]=f[3,i]) and(f[3,i]=f[4,i]) and((f[4,i]=1) or(f[4,i]=2))then
24         begin
25                 m:=num;
26                 flag:=1;
27         end;
28      end;
29      if (f[1,1]=f[2,2]) and(f[1,1]=f[3,3]) and (f[1,1]=f[4,4]) and((f[4,4]=1) or(f[4,4]=2))then
30      begin
31         m:=num;
32         flag:=1;
33      end;
34      if (f[1,4]=f[2,3]) and(f[1,4]=f[3,2]) and(f[1,4]=f[4,1]) and((f[1,4]=1) or(f[1,4]=2))then
35      begin
36         m:=num;
37         flag:=1;
38      end;
39      if (m<min) and (flag=1) then
40      begin
41         min:=m;
42         exit;
43      end;
44 
45                 for k:=1 to 4 do
46                 if (x+fx[k]>0) and(x+fx[k]<5) and (y+fy[k]>0) and(y+fy[k]<5) and (f[x+fx[k],y+fy[k]]=co) then
47                  begin
48 
49                     f[x,y]:=f[x+fx[k],y+fy[k]];
50                     f[x+fx[k],y+fy[k]]:=0;
51                     if co=1 then co:=2 else co:=1;
52                     for i:=1 to 4 do
53                         for j:=1 to 4 do
54                         if f[i,j]=0 then
55                     dfs(i,j,num+1,co);
56                     if co=1 then co:=2 else co:=1;
57 
58                     f[x+fx[k],y+fy[k]]:=F[X,Y];
59                     f[x,y]:=0;
60                  end;
61 
62 
63  end;
64 
65 begin
66     min:=maxlongint;
67     for i:=1 to 4 do
68     begin
69         for j:=1 to 4 do
70         begin
71             read(ch);
72             if ch='W' then f[i,j]:=1;
73             if ch='B' then f[i,j]:=2;
74         end;
75         readln;
76     end;
77     for i:=1 to 4 do
78         for j:=1 to 4 do
79         if f[i,j]=0 then
80         begin
81             dfs(i,j,0,1);
82             dfs(i,j,0,2);
83         end;
84      writeln(min);
85 end.

DFS

 1 program FourChess;
 2 const fx:array[1..4] of longint=(1,-1,0,0);
 3       fy:array[1..4] of longint=(0,0,1,-1);
 4 var
 5 f:array[1..4,1..4] of longint;
 6 i,j:longint;
 7 min:longint;
 8 ch:char;
 9 
10 
11 procedure dfs(x,y,num,co:longint);
12 var i,j,k,m,flag:longint;
13 begin
14     flag:=0;
15      if num>=min then exit;
16      for i:=1 to 4 do
17      begin
18         if (f[i,1]=f[i,2]) and(f[i,2]=f[i,3]) and(f[i,3]=f[i,4])and((f[i,4]=1) or(f[i,4]=2)) then
19         BEGIN
20             m:=num;
21             flag:=1;
22         end;
23         if (f[1,i]=f[2,i]) and(f[2,i]=f[3,i]) and(f[3,i]=f[4,i]) and((f[4,i]=1) or(f[4,i]=2))then
24         begin
25                 m:=num;
26                 flag:=1;
27         end;
28      end;
29      if (f[1,1]=f[2,2]) and(f[1,1]=f[3,3]) and (f[1,1]=f[4,4]) and((f[4,4]=1) or(f[4,4]=2))then
30      begin
31         m:=num;
32         flag:=1;
33      end;
34      if (f[1,4]=f[2,3]) and(f[1,4]=f[3,2]) and(f[1,4]=f[4,1]) and((f[1,4]=1) or(f[1,4]=2))then
35      begin
36         m:=num;
37         flag:=1;
38      end;
39      if (m<min) and (flag=1) then
40      begin
41         min:=m;
42         exit;
43      end;
44 
45                 for k:=1 to 4 do
46                 if (x+fx[k]>0) and(x+fx[k]<5) and (y+fy[k]>0) and(y+fy[k]<5) and (f[x+fx[k],y+fy[k]]=co) then
47                  begin
48 
49                     f[x,y]:=f[x+fx[k],y+fy[k]];
50                     f[x+fx[k],y+fy[k]]:=0;
51                     if co=1 then co:=2 else co:=1;
52                     for i:=1 to 4 do
53                         for j:=1 to 4 do
54                         if f[i,j]=0 then
55                     dfs(i,j,num+1,co);
56                     if co=1 then co:=2 else co:=1;
57 
58                     f[x+fx[k],y+fy[k]]:=F[X,Y];
59                     f[x,y]:=0;
60                  end;
61 
62 
63  end;
64 
65 begin
66     min:=20;
67     for i:=1 to 4 do
68     begin
69         for j:=1 to 4 do
70         begin
71             read(ch);
72             if ch='W' then f[i,j]:=1;
73             if ch='B' then f[i,j]:=2;
74         end;
75         readln;
76     end;
77     for i:=1 to 4 do
78         for j:=1 to 4 do
79         if f[i,j]=0 then
80         begin
81             dfs(i,j,0,1);
82             dfs(i,j,0,2);
83         end;
84      writeln(min);
85 end.

BFS