Tic-Tac-Toe

Description

Kim likes to play Tic-Tac-Toe.

Given a current state, and now Kim is going to take his next move. Please tell Kim if he can win the game in next 2 moves if both player are clever enough.

Here “next 2 moves” means Kim’s 2 move. (Kim move,opponent move, Kim move, stop).

Game rules:

Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.

Input

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Each test case contains three lines, each line three string(“o” or “x” or “.”)(All lower case letters.)

x means here is a x

o means here is a o

. means here is a blank place.

Next line a string (“o” or “x”) means Kim is (“o” or “x”) and he is going to take his next move.

Output

For each test case:

If Kim can win in 2 steps, output “Kim win!”

Otherwise output “Cannot win!”

Sample Input

. . .

o x o

o . x

x x o

o x .

. o .

. . x

Sample Output

Cannot win!

Kim win!

题目意思：这是一个三子相连获胜的游戏，不管是横竖斜相连，只要能够连成一条线即可，问Kim在给出的局势下先手是否能取得胜利。.代表双方没有下过棋，xo代表双方各自下的棋，先给t组样例，每一组样例包含一个3*3的矩阵棋盘，之后一个棋子代表着Kim下的棋。

解题思路：开始做的时候一点头绪都没有，看了看网上的题解大多都是暴力模拟，然而我同学找了找规律，a了这道题，开始我以为是后台样例太水才让他侥幸过了，不过后来我试了试很多样例，才明白后台的数据应该是按照两人正常博弈给出的，而不是随便乱给的数据。这里我们就来使用这种找规律的方法来分析一下这道题。

1.如果两人下的棋的步数小于2，也就是只下了一步或者还没有开始，那么肯定Kim是不可能在两步之内取得胜利的。还没有开始的话两步就算对方没有去阻拦也不够三个棋子，只走了一步，接下来的两步中对方一去阻拦，也不会连成一条线。

2.如果这时候步数大于等于2了，能否取得胜利的关键就是能否占领了最中间的位置或者在最中间的位置双方都没有下过棋。

如下样例

（1）这一种情况下大家都走了两步，但是Kim占领了最中间的位置，那么他下一步只要在占领左下角的位置，之后他就会有两条线可以三子相连不管另一个怎么样围堵，都能取得胜利。

（2）这种情况在占领了最中间位置的情况下，只需要一步就能取胜，即下左下角那一步。

这种局势也是类似的

（3）在这种双方都没有占领最中间位置的情况下，先手会必胜，会有两种下法，1是占领最中间位置，2是占领其他位置构成两条会完成的三连线。

这种局势下占领最中间的位置，正负对角线会出现两条未完成的三连线，无论对方如何围堵，都会取得胜利。

这种局势想要取得胜利就不能去占领最中间的位置了。

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<algorithm>
 5 using namespace std;
 6 int main()
 7 {
 8     int i,j,k,l,m,n,t,q;
 9     char a[5][5],b;
10     scanf("%d",&t);
11     for(l=0;l<t;l++)
12     {
13         k=0;q=0;
14         for(i=0;i<3;i++)
15             for(j=0;j<3;j++)
16                 scanf(" %c",&a[i][j]);
17         scanf(" %c",&b);
18         for(i=0;i<3;i++)
19             for(j=0;j<3;j++)
20                 if(a[i][j]==b)
21                     q++;
22         if(q<2)
23             printf("Cannot win!
");
24         else
25         {
26             if(a[1][1]==b||a[1][1]=='.')
27                 printf("Kim win!
");
28             else
29                 printf("Cannot win!
");
30         }
31     }
32     return 0;
33 }

在这里有一个网站可以和人机玩一下这个游戏。

http://www.calculatorcat.com/games/tic_tac_toe.phtml

对于这个游戏有几个结论：

1.先手只要经营得当一定会取得胜利。（一开始就占领最中间的位置）

可以这样理解先手一上来就为了构建有利于自己的局势，而后手的第一步并没有太大的意义即使是为了构建有利于自己的局势，但也还落后于先手，后面的局势还要疲于应对先手防范其三子相连，可以说一开始后手就落于下风。

2.如果让后手占领了最中间的位置，先手最多只能与其打平，而不会取得胜利。

中间位置对双方都很重要，中间位置对四面八方起着一个辐射的作用，占领中间意味着可以有多条未连接三子相连，即使对方封锁了其中的一条，但仍旧还有一条通路，可以说先手占领了最中间的位置可以说是利于不败之地了。而后手占领了中间位置，先手之前构筑的优势尽失，最多先手只能打平。