首页 > > 程序设计 > C/C++ >

1004 四子连棋未完成

2018-06-17 22:45:19来源：未知阅读 ()

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

分类标签 Tags 点此展开

  1 #include<iostream>
  2 #include<cstdio>
  3 using namespace std;
  4 const int MAXN=10;
  5 int map[MAXN][MAXN];
  6 int vis[MAXN][MAXN][MAXN][MAXN];
  7 int kong1x,kong1y;
  8 int kong2x,kong2y;
  9 int hang[MAXN];// 储存每一行有多少个黑棋子 
 10 int lie[MAXN];
 11 int leftdjx;//左对角线 
 12 int rightdjx;// 右对角线 
 13 int ans=0x7fffffff;
 14 int xx[5]={-1,+1,0,0};
 15 int yy[5]={0,0,-1,+1};
 16 int how;// 1表示应该走黑棋    2表示白棋 
 17 void dfs(int k1x,int k1y,int k2x,int k2y,int step)
 18 {
 19     for(int i=1;i<=4;i++)
 20     {
 21         if(leftdjx==4||rightdjx==4||hang[i]==4||(hang[i]==0&&k1x!=i&&k2x!=i)||lie[i]==4||(lie[i]==0&&k1y!=i&&k2y!=i))
 22         {
 23             if(step<ans)
 24             ans=step;
 25             return ;
 26         }
 27     }
 28     if(step>ans)
 29     return;
 30     for(int i=0;i<4;i++)
 31     {
 32         int flag=0;
 33         int wx=k1x+xx[i];
 34         int wy=k1y+yy[i];
 35         if(((map[wx][wy]==how)||how==2)&&wx<=4&&wx>=1&&wy<=4&&wy>=1&&map[wx][wy]!=2&&vis[k1x][k1y][wx][wy]==0)
 36         {
 37             if(map[wx][wy]==1)
 38             how=0;
 39             else if(map[wx][wy]==0)
 40             how=1;
 41             if(map[wx][wy]==1)
 42             {
 43                 hang[k1x]++;
 44                 hang[wx]--;
 45                 lie[k1y]++;
 46                 lie[wy]--;
 47                 if(k1x==k1y)
 48                 leftdjx++;
 49                 if(k1x+k1y==5)
 50                 rightdjx++;
 51                 flag=1;
 52                 if(wx==wy)
 53                 leftdjx--;
 54                 if(wx+wy==5)
 55                 rightdjx--;
 56             }
 57             vis[k1x][k1y][wx][wy]=1;
 58             map[k1x][k1y]=map[wx][wy];
 59             map[wx][wy]=2;
 60             dfs(wx,wy,k2x,k2y,step+1);
 61             /*if(map[wx][wy]==1)
 62             how=0;
 63             else if(map[wx][wy]==0)
 64             how=1;*/
 65             vis[k1x][k1y][wx][wy]=0;
 66             map[wx][wy]=map[k1x][k1y];
 67             map[k1x][k1y]=2;
 68             if(flag==1)
 69             {
 70                 hang[k1x]--;
 71                 hang[wx]++;
 72                 lie[k1y]--;
 73                 lie[wy]++;
 74                 if(k1x==k1y)
 75                 leftdjx--;
 76                 if(k1x+k1y==5)
 77                 rightdjx--;
 78                 if(wx==wy)
 79                 leftdjx++;
 80                 if(wx+wy==5)
 81                 rightdjx++;
 82             }
 83         }
 84     }
 85     for(int i=0;i<4;i++)
 86     {
 87         int flag=0;
 88         int wx=k2x+xx[i];
 89         int wy=k2y+yy[i];
 90         if(((map[wx][wy]==how)||how==2)&&wx<=4&&wx>=1&&wy<=4&&wy>=1&&map[wx][wy]!=2&&vis[k2x][k2y][wx][wy]==0)
 91         {
 92             if(map[wx][wy]==1)
 93             how=0;
 94             else if(map[wx][wy]==0)
 95             how=1;
 96             if(map[wx][wy]==1)
 97             {
 98                 hang[k2x]++;
 99                 hang[wx]--;
100                 lie[k2y]++;
101                 lie[wy]--;
102                 if(k2x==k2y)
103                 leftdjx++;
104                 if(k2x+k2y==5)
105                 rightdjx++;
106                 flag=1;
107                 if(wx==wy)
108                 leftdjx--;
109                 if(wx+wy==5)
110                 rightdjx--;
111             }
112             vis[k2x][k2y][wx][wy]=1;
113             map[k2x][k2y]=map[wx][wy];
114             map[wx][wy]=2;
115             dfs(k1x,k1y,wx,wy,step+1);
116             /*if(map[wx][wy]==1)
117             how=0;
118             else if(map[wx][wy]==0)
119             how=1;*/
120             vis[k2x][k2y][wx][wy]=0;
121             map[wx][wy]=map[k2x][k2y];
122             map[k2x][k2y]=2;
123             if(flag==1)
124             {
125                 hang[k2x]--;
126                 hang[wx]++;
127                 lie[k2y]--;
128                 lie[wy]++;
129                 if(k2x==k2y)
130                 leftdjx--;
131                 if(k2x+k2y==5)
132                 rightdjx--;
133                 if(wx==wy)
134                 leftdjx++;
135                 if(wx+wy==5)
136                 rightdjx++;
137             }
138         }
139     }
140 }
141 int main()
142 {
143     for(int i=1;i<=4;i++)
144     {
145         for(int j=1;j<=4;j++)
146         {
147             char c;
148             cin>>c;
149             if(c=='B')
150             {
151                 map[i][j]=1;// 黑色棋子 
152                 hang[i]++;
153                 lie[j]++;
154                 if(i==j)leftdjx++;
155                 if(i+j==5)rightdjx++;
156             }
157             else if(c=='W')
158             {
159                 map[i][j]=0;//白色棋子 
160             }
161             else
162             {
163                 map[i][j]=2;
164                 if(kong1x==0&&kong1y==0)
165                 {
166                     kong1x=i;
167                     kong1y=j;
168                 }
169                 else
170                 {
171                     kong2x=i;
172                     kong2y=j;
173                 }
174             }
175         }
176     }
177     how=2;
178     dfs(kong1x,kong1y,kong2x,kong2y,0);
179     printf("%d",ans);
180     return 0;
181 }