Problem B: Tic Tac Toe

Problem B: Tic Tac Toe

时间: 1ms        内存:128M

描述:

Problem B: Tic Tac Toe

Tic Tac Toe is a child's game played on a 3 by 3 grid. One player, X, starts by placing an X at an unoccupied grid position. Then the other player, O, places an O at an unoccupied grid position. Play alternates between X and O until the grid is filled or one player's symbols occupy an entire line (vertical, horizontal, or diagonal) in the grid.

We will denote the initial empty Tic Tac Toe grid with nine dots. Whenever X or O plays we fill in an X or an O in the appropriate position. The example below illustrates each grid configuration from the beginning to the end of a game in which X wins.

...  X..  X.O  X.O  X.O  X.O  X.O  X.O
...  ...  ...  ...  .O.  .O.  OO.  OO.
...  ...  ...  ..X  ..X  X.X  X.X  XXX

Your job is to read a grid and to determine whether or not it could possibly be part of a valid Tic Tac Toe game. That is, is there a series of plays that can yield this grid somewhere between the start and end of the game?

The first line of input contains N, the number of test cases. 4N-1 lines follow, specifying N grid configurations separated by empty lines. For each case print "yes" or "no" on a line by itself, indicating whether or not the configuration could be part of a Tic Tac Toe game.

输入:

输出:

示例输入:

2
X.O
OO.
XXX

O.X
XX.
OOO

示例输出:

yes
no

提示:

参考答案(内存最优[800]):

#include <stdio.h>

char g[3][4];

int i,j,k,m,n,N,xcount,ocount;

int win(char c){
   int i,j;
   for (i=0;i<3;i++) {
      for (j=0;j<3 && g[i][j]==c;j++);
      if (j==3) return 1;
      for (j=0;j<3 && g[j][i]==c;j++);
      if (j==3) return 1;
   }
   for (i=0;i<3 && g[i][i]==c;i++);
   if (i==3) return 1;
   for (i=0;i<3 && g[i][2-i]==c;i++);
   if (i==3) return 1;
   return 0;
}

main(){
   scanf("%d",&N);
   while (N--){
      scanf(" %s %s %s",g[0],g[1],g[2]);
      xcount = ocount = 0;
      for (i=0;i<3;i++) for (j=0;j<3;j++) {
         if (g[i][j] == 'X') xcount++;
         if (g[i][j] == 'O') ocount++;
      }
      /*printf("x %d o %d xwin %d owin %d\n",xcount,ocount,win('X'),win('O'));*/
      if (
         ocount > xcount || xcount > ocount + 1
         || win('X') && win('O') 
         || win('O') && xcount != ocount
         || win('X') && xcount == ocount
      ) {
         printf("no\n");
         continue;
      }
      printf("yes\n");
   }
}

参考答案(时间最优[0]):

#include <stdio.h>

char g[3][4];

int i,j,k,m,n,N,xcount,ocount;

int win(char c){
   int i,j;
   for (i=0;i<3;i++) {
      for (j=0;j<3 && g[i][j]==c;j++);
      if (j==3) return 1;
      for (j=0;j<3 && g[j][i]==c;j++);
      if (j==3) return 1;
   }
   for (i=0;i<3 && g[i][i]==c;i++);
   if (i==3) return 1;
   for (i=0;i<3 && g[i][2-i]==c;i++);
   if (i==3) return 1;
   return 0;
}

main(){
   scanf("%d",&N);
   while (N--){
      scanf(" %s %s %s",g[0],g[1],g[2]);
      xcount = ocount = 0;
      for (i=0;i<3;i++) for (j=0;j<3;j++) {
         if (g[i][j] == 'X') xcount++;
         if (g[i][j] == 'O') ocount++;
      }
      /*printf("x %d o %d xwin %d owin %d\n",xcount,ocount,win('X'),win('O'));*/
      if (
         ocount > xcount || xcount > ocount + 1
         || win('X') && win('O') 
         || win('O') && xcount != ocount
         || win('X') && xcount == ocount
      ) {
         printf("no\n");
         continue;
      }
      printf("yes\n");
   }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注