首页 > 代码库 > 1004 四子连棋 未完成
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 else162 {163 map[i][j]=2;164 if(kong1x==0&&kong1y==0)165 {166 kong1x=i;167 kong1y=j;168 }169 else170 {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 }
1004 四子连棋 未完成
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。