五子棋的历史
连子棋类游戏起源很早&＃xff0c;在四千年前的两河文明就有古西亚连棋。
五子棋则咸信是流传于古中国的传统棋种之一&＃xff0c;至今仍在民间广泛流传&＃xff0c;规则相当简单。或许因没有形成一套独立完整的棋种理论及文化内涵&＃xff0c;更无制定公平完善的规则来解决黑白平衡问题&＃xff0c;一直没有得到发展&＃xff0c;所以没有像围棋、象棋等传统棋类流传广泛&＃xff0c;导致缺少可考古的棋具&＃xff0c;也没像直棋、方棋等乡土棋类记载在地方县志、古人笔记等文献。
五子棋在传入日本后&＃xff0c;被日本人发扬光大&＃xff0c;自1899年日本棋士黒岩涙香证明了原始规则的五子棋先下必胜后&＃xff0c;五子棋迈入一条不断改良的道路&＃xff0c;经过数十年的修改、验证、再修改&＃xff0c;最终发展出加入禁手的五子棋&＃xff0c;并经过公开征名&＃xff0c;称为连珠&＃xff08;RENJU&＃xff09;&＃xff0c;因此规则在日本成型&＃xff0c;又称为日式规则或连珠规则。原始规则在中国依然有人在玩&＃xff0c;也被称为无禁规则、自由规则&＃xff0c;有软件可验证黑手必胜&＃xff08;这个稍后再证明&＃xff09;。
连珠规则禁止先下的黑棋下出双活三、双四、长连&＃xff08;超过五子以上的连线&＃xff09;下出则判败&＃xff0c;此举限制黑棋的取胜方式&＃xff0c;白棋则增加逼迫黑子下出禁手来取胜的手 段&＃xff0c;使黑棋的优势稍稍减少。不过禁手也许对初学者来说是一种障碍&＃xff0c;但下久后会发现&＃xff0c;禁手使得双方棋手必需更加精准的掌握棋子的落点&＃xff0c;增加了连珠的技术性、 复杂性及趣味性。
又过了几十年&＃xff0c;人们发现单单加入禁手&＃xff0c;尚无法完全平衡黑棋一子之先的优势&＃xff0c;因此在国际比赛使用的“RIF规则”&＃xff0c;在连珠规则的基础上&＃xff0c;又加入了三手交换及五手两打&＃xff0c;算第一个可以真正合乎公平竞技的职业规则。
Problem——该问题,是用一串二维数组装载的字符串&＃xff0c;用.表示空&＃xff0c;用W表示白棋&＃xff0c;用B表示黑棋&＃xff0c;来判断目前的局面中的当前走棋的一方是否赢了整盘棋。
Solve:
/*
该程序可以判定当前的一方是否获胜&＃xff0c;如果暂时没有获胜或者已经告负&＃xff0c;本
程序会有相应的输出。
AI的策略基本上和连连看的相似&＃xff0c;也用的是queue容器&＃43;BFS
&＃xff08;1&＃xff09;判断当前局势&＃xff0c;利用目前棋盘上黑子和白子的数量进行比较
&＃xff08;2&＃xff09;五子连环必须是恰好有五个子&＃xff0c;也就是说&＃xff0c;沿端点方向上的点应该是空格的
&＃xff08;3&＃xff09;表面上是八个方向&＃xff0c;实际上考虑到对称性&＃xff0c;四个方向即可
&＃xff08;4&＃xff09;在for循环的条件判断上加上flag&＃xff0c;找到一例&＃xff0c;即可退出循环
*/
2 #include
3 using namespace std;
4
5 struct Node //每个点有一个坐标&＃xff0c;最大连通数以及方向
6 {
7 char x,y,time,dirc;
8 bool no_stone;
9 };
10
11 char map[15][15],c;//定义一个二维数组&＃xff0c;表示棋盘,c表示现在轮到谁
12
13 int dir[4][2]&＃61;{{0,1},{1,0},{1,-1},{1,1}};//四个方向
14
15 //BFS搜索&＃xff0c;和之前的连连看类似
16 bool bfs(int x,int y)
17 {
18 queue
19 Node first,next;
20 int i;
21 first.x&＃61;x;
22 first.y&＃61;y;
23 first.no_stone&＃61;false;
24 first.time&＃61;1;
25 first.dirc&＃61;-1;
26 Q.push(first);
27
28 while(!Q.empty())
29 {
30 first&＃61;Q.front();
31 Q.pop();
32 //从第一个点开始&＃xff0c;保证有且仅有五个是连在一起的&＃xff0c;用no_stone标识没有多连
33 if(first.time&＃61;&＃61;5&&first.no_stone)
34 {
35 return true;
36 }
37 for(i&＃61;0;i<4;i&＃43;&＃43;)
38 {
39 //初始方向不确定
40 if(first.dirc&＃61;&＃61;-1||first.dirc&＃61;&＃61;i)
41 {
42 next.x&＃61;first.x&＃43;dir[i][0];
43 next.y&＃61;first.y&＃43;dir[i][1];
44 if(next.x>&＃61;0&&next.x<15&&next.y>&＃61;0&&next.y<15)
45 {
46 next.dirc&＃61;i;
47 next.time&＃61;first.time&＃43;1;
48 //唯独不标识对手的棋子&＃xff0c;自己的棋子和空棋子用no_stone区分
49 if(map[next.x][next.y]&＃61;&＃61;c)
50 {
51 next.no_stone&＃61;first.no_stone;
52 Q.push(next);
53 }
54 else if(map[next.x][next.y]&＃61;&＃61;&＃39;.&＃39;&&!first.no_stone)
55 {
56 next.no_stone&＃61;true;
57 Q.push(next);
58 }
59 }
60 }
61 }
62 }
63 return false;
64 }
65
66 int main()
67 {
68 int T;
69 scanf("%d",&T);
70 while(T--)
71 {
72 int i,j;
73 int white_num&＃61;0,black_num&＃61;0;
74 getchar(); //读入一个回车键
75 for(i&＃61;0;i<15;i&＃43;&＃43;)
76 {
77 gets(map[i]);
78 }
79 for(i&＃61;0;i<15;i&＃43;&＃43;)
80 {
81 for(j&＃61;0;j<15;j&＃43;&＃43;)
82 {
83 if(map[i][j]&＃61;&＃61;&＃39;W&＃39;)
84 {
85 white_num&＃43;&＃43;;
86 }
87 else if(map[i][j]&＃61;&＃61;&＃39;B&＃39;)
88 {
89 black_num&＃43;&＃43;;
90 }
91 }
92 }
93 //记录黑白棋子的数量&＃xff0c;主要是判断当前下棋方是黑还是白
94 if(black_num>white_num)
95 {
96 c&＃61;&＃39;W&＃39;;
97 }
98 else
99 {
100 c&＃61;&＃39;B&＃39;;
101 }
102 bool flag&＃61;true;
103 //只要找到一个“五子连”就可以了
104 for(i&＃61;0;i<15&&flag;i&＃43;&＃43;)
105 {
106 for(j&＃61;0;j<15&&flag;j&＃43;&＃43;)
107 {
108 if(map[i][j]&＃61;&＃61;c)
109 {
110 flag&＃61;!bfs(i,j);
111 }
112 }
113 }
114 if(flag) printf("NO\n");
115 else printf("YES\n");
116 }
117 return 0;
118 }
京公网安备 11010802041100号