Problem L Tic-Tac-Toe

Accept: 94    Submit: 184

Time Limit: 1000 mSec    Memory Limit : 262144 KB

 Problem 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

3

. . .

. . .

. . .

o

o x o

o . x

x x o

x

o x .

. o .

. . x

o

 Sample Output

Cannot win!

Kim win!

Kim win!

 

九宫棋Kim先下两步之内是否可以胜利

 

题解下次贴

 

#include 
      
         #include 
       
          #include 
        
           #include 
         
            #include 
          
             using namespace std;  char map[4][4];  int s[4][4],t,sum,k,cnt;  bool judge(int x,int y){      if((x+y)%2==1){
    //当此时这个格子的行列的和为奇数时          cnt=0,sum=0; //cnt代表可能胜利的次数         for(int i=1;i<=3;i++){              sum+=s[i][y];          }          sum*=k;  //同是负数相乘为正数        if(sum==2)  //空白数为2时代表可以            return true;          else if(sum==1)  //当sum和为1时，此时可能胜利            cnt++;          sum=0;  //注意，此时一定要重置sum，因为sum在这个函数的前面后面的含义不同        for(int i=1;i<=3;i++){              sum+=s[x][i];//计算此时画相同的符号的个数之和        }          sum*=k;          if(sum==2)  //如果画相同符号的和为2，代表画下一个一定会胜利            return true;          else if(sum==1)  //如果此时画的相同的符合为1，代表可能胜利            cnt++;          if(cnt==2){  //当可能胜利的次数超过2时一定可以胜利            return true;          }      }      else {  //当此时这个各自的行列的和为偶数时          cnt=0,sum=0;          for(int i=1;i<=3;i++){              sum+=s[i][y];          }          sum*=k;          if(sum==2)              return true;          else if(sum==1)              cnt++;          sum=0;          for(int i=1;i<=3;i++){              sum+=s[x][i];          }          sum*=k;          if(sum==2)              return true;          else if(sum==1)              cnt++;          sum=0;          if(x==y){  //代表这个空白所在的地方在斜线上            for(int i=1;i<=3;i++){                  sum+=s[i][i];              }              sum*=k;                            if(sum==2)                  return true;              else if(sum==1)                  cnt++;          }          else {              for(int i=1;i<=3;i++){                  sum+=s[i][4-i];              }              sum*=k;                            if(sum==2)                  return true;              else if(sum==1)                  cnt++;          }          if(cnt>=2){              return true;          }      }      return false;  }    int main(){      char st;      int flag;      scanf("%d",&t);      while(t--){          flag=0;          memset(s,0,sizeof(0));          for(int i=1;i<=3;i++){              for(int j=1;j<=3;j++){                  cin>>map[i][j];                  if(map[i][j]=='.')  s[i][j]=0;                  else if(map[i][j]=='o') s[i][j]=1;                  else if(map[i][j]=='x') s[i][j]=-1;              }          }          cin>>st;  //代表此时Kim所用的符号        if(st=='o') k=1;          else if (st=='x') k=-1;          for(int i=1;i<=3;i++){              for(int j=1;j<=3;j++){                  if(map[i][j]=='.'){                      if(judge(i,j))                          flag=1;                  }              }          }          if(flag) puts("Kim win!");              else    puts("Cannot win!");      }      return 0;  }