CCCHK '08 J4 - Tic-tac-toe

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

The game tic-tac-toe is played on a 3 \times 3 grid. Two players place cross (X) and nought (O) alternatively. The game ends whenever a player can make a line of 3 of their mark vertically, horizontally, or diagonally; or all slots are occupied.

Figure 1: A snapshot of a game.

In this problem, you are given a snapshot of a game and you need to verify if it is valid. You can assume that the first mark to be placed is always a cross.

Input Specification

The first input is a number T specifying the number of test cases (1 \le T \le 20\,000). For each test case, 9 characters on each line are used to denote a snapshot, each containing only . (period, representing an empty slot), X, and O. The first 3 characters are the contents of the first row, the next 3 are for the second row, etc. For example, the snapshot of the example is represented as follows:


Output Specification

For each test case, output yes if the snapshot is valid; no, otherwise.

Sample Input


Sample Output



  • 1
    gj504772  commented on Oct. 8, 2022, 10:31 p.m. edited

    What does CCCHK stand for?

    • 3
      d  commented on Oct. 11, 2022, 6:44 a.m.

      Canadian Computing Competition Hong Kong

  • 2
    Noam527  commented on May 11, 2017, 12:02 p.m.

    I'm pretty sure "valid" as if it's possible to reach this state from the beginning... not that hard to understand

  • 7
    ASentientBot  commented on April 25, 2017, 3:03 p.m.

    Does "valid" just mean that (1) no more than one person has won and (2) there are not more O's than X's?

    • 1
      IanHu  commented on Dec. 17, 2018, 1:41 a.m.

      and also, when "O" is win, number of "X" cannot be greater than "O": "XO. XOX .OX" is invalid

    • 1
      TypicalToxic  commented on May 8, 2017, 3:23 a.m.

      Bump, Clarification on valid?