codevs 1004 四子连棋

1004 四子连棋

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

数据范围及提示 Data Size & Hint

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 int map[6][6];
 8 int move[5]={0,1,0,-1,0};
 9 int bor;
10 string _;int x[3],y[3],ans=0x7fffffff;
11 bool can(int x,int y,int z)
12 {
13     if(x>=1&&x<=4&&y>=1&&y<=4&&z!=map[x][y])return 1;else return 0;
14 }
15 bool check()
16 {
17     if(map[1][1]==map[1][2]&&map[1][2]==map[1][3]&&map[1][3]==map[1][4])return 1;
18     if(map[2][1]==map[2][2]&&map[2][2]==map[2][3]&&map[2][3]==map[2][4])return 1;
19     if(map[3][1]==map[3][2]&&map[3][2]==map[3][3]&&map[3][3]==map[3][4])return 1;
20     if(map[4][1]==map[4][2]&&map[4][2]==map[4][3]&&map[4][3]==map[4][4])return 1;
21     if(map[1][1]==map[2][2]&&map[2][2]==map[3][3]&&map[3][3]==map[4][4])return 1;
22     if(map[1][4]==map[2][3]&&map[2][3]==map[3][2]&&map[3][2]==map[4][1])return 1;
23     else return 0;
24 }
25 bool dfs(int x1,int y1,int who,int x2,int y2,int step)
26 {
27     if(step==bor)
28     {
29         if(check())return 1;
30         else return 0;
31     }
32     int next_x1,next_x2,next_y1,next_y2;
33     for(int i=0;i<4;i++)
34     {
35         next_x1=x1+move[i];
36         next_y1=y1+move[i+1];
37         next_x2=x2+move[i];
38         next_y2=y2+move[i+1];
39         if(can(next_x1,next_y1,who))
40         {
41             int sssy1;
42             if(who==1)
43             sssy1=2;else sssy1=1;
44             swap(map[x1][y1],map[next_x1][next_y1]);
45             if(dfs(next_x1,next_y1,sssy1,x2,y2,step+1))return 1;
46             swap(map[x1][y1],map[next_x1][next_y1]);
47         }
48         if(can(next_x2,next_y2,who))
49         {
50             int sssy2;
51             if(who==1)sssy2=2;else sssy2=1;
52             swap(map[x2][y2],map[next_x2][next_y2]);
53             if(dfs(x1,y1,sssy2,next_x2,next_y2,step+1))return 1;
54             swap(map[x2][y2],map[next_x2][next_y2]);
55         }
56     }
57     return 0;
58 }
59 int main()
60 {
61     int pppppp=1;
62     for(int i=1;i<=4;i++)
63     {
64         cin>>_;
65         for(int j=0;j<4;j++)
66         {
67             if(_[j]=='B')map[i][j+1]=1;
68             else if(_[j]=='W')map[i][j+1]=2;
69             else 
70             {
71                 x[pppppp]=i;
72                 y[pppppp++]=j+1;
73             }
74         }
75     }
76     for(bor=1;;bor++)
77     {
78         if(dfs(x[1],y[1],2,x[2],y[2],0))break;
79         if(dfs(x[1],y[1],1,x[2],y[2],0))break;
80     }
81     printf("%d",bor);
82 }