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

5

数据范围及提示 Data Size & Hint

hi

分类标签 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

27610
来自专栏数据结构与算法

BZOJ 5248: [2018多省省队联测]一双木棋(对抗搜索)

1510
来自专栏chenjx85的技术专栏

leetcode-458-Poor Pigs

1804
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2493
来自专栏数说工作室

【SAS Says】基础篇:基本统计、相关分析与回归分析

特别说明:本节【SAS Says】基础篇:SAS宏初步,用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择 S...

4315
来自专栏数说工作室

【SAS Says】基础篇:8. 相关、回归等初步统计

SAS是一个专业的统计软件,前面我们介绍了很多数据管理、输出美化的东西,本节终于要介绍一点SAS做统计的知识了,不过,在基础篇中我们只大概介绍一下,更多统计分析...

3116
来自专栏desperate633

LintCode 房屋染色题目代码

这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用...

942
来自专栏BestSDK

10行代码告诉你,为什么说Python数据可视化是一件艺术品

1. 画散点图 画散点图用plt.scatter(x,y)。画连续曲线在下一个例子中可以看到,用到了plt.plot(x,y)。 plt.xticks(loc,...

4286
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(上)

因为这一章的内容基本上都是涉及向量的,先来一个2D向量类:Vector2D.as (再次强烈建议不熟悉向量运算的童鞋,先回去恶补一下高等数学-07章空间解释几何...

2136
来自专栏锦小年的博客

复杂网络(1)--图论的基本理论

1 图论的基本概念 1.1 图(graph)及其分类 (1) 图的定义:图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组,记为G=(...

26210

扫码关注云+社区

领取腾讯云代金券