題目網址:A - Tic-Tac-Toe-Tomek

題目概述

給定一個圈圈叉叉的遊戲狀態,判斷給定的狀態屬於下列哪一種:

  • X 獲勝
  • O 獲勝
  • 平手
  • 遊戲尚未結束

題目所給的圈圈叉叉跟我們以往玩的有些許不同,它是由 4 × 4 的方格組成。而勝利條件除了橫向直向對角線都存在相同元素外,也可以由 3 個相同元素加上一個 T 來獲得勝利。

Technique Detail

small case:

  • 1 ≤ T ≤ 10

large case:

  • 1 ≤ T ≤ 1000

輸入格式

測試資料由一個整數 T 開始,表示接下來會有 T 比測試資料。而每筆測試資料都包含四行且每行有四個字元,即為圈圈叉叉的狀態。X 表示當前格子放置了 X,O 則表示放置了 O,T 則表示放置了 T,而 . 則表示當前格子為空白。另外,在每一筆測試資料後都會有一個空行。

輸出格式

輸出給定的圈圈叉叉的狀態為何,如下:

  • X won
  • O won
  • Draw
  • Game has not completed

解題思路

很明顯的這題就是 Qualification Round 的水題,做法非常容易。先是直接判斷 X 跟 O 有沒有人贏,檢查橫向直向與對角線。若有人勝利則輸出該勝利者,沒有的話在判斷是不是還有空格。如果還存在空格,那麼表示「遊戲尚未結束」,如果不存在空格了,那就輸出「平手」。

Time Complexity: O(1)

Source Code

Source code on gist.