題目網址: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

/*=============================================================================
# FileName: qround - a - Tic-Tac-Toe-Tomek.cpp
# Desc: Google Code Jam - Qualification Round - A - Tic-Tac-Toe-Tomek
# Author: KuoE0
# Email: kuoe0.tw@gmail.com
# HomePage: http://kuoe0.ch/
# Version: 0.0.1
# LastChange: 2013-04-14 16:19:38
# History:
=============================================================================*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
bool checkFull( char board[][ 10 ] ) {
for ( int i = 0; i < 4; ++i )
for ( int j = 0; j < 4; ++j )
if ( board[ i ][ j ] == '.' )
return false;
return true;
}
bool checkRowCol( char board[][ 10 ], char k, int rc, bool dir ) {
int cnt = 0, T = 0;
for ( int i = 0; i < 4; ++i ) {
char c = board[ dir ? i : rc ][ dir ? rc : i ];
cnt += c == k ? 1 : 0;
T += c == 'T' ? 1 : 0;
}
return cnt == 4 || ( cnt == 3 && T == 1 );
}
bool checkDiagonal( char board[][ 10 ], char k, bool dir ) {
int cnt = 0, T = 0;
for ( int i = 0; i < 4; ++i ) {
int c = board[ i ][ dir ? 3 - i : i ];
cnt += c == k ? 1 : 0;
T += c == 'T' ? 1 : 0;
}
return cnt == 4 || ( cnt == 3 && T == 1 );
}
bool checkWin( char board[][ 10 ], char k ) {
for ( int i = 0; i < 4; ++i )
if ( checkRowCol( board, k, i, 0 ) || checkRowCol( board, k, i, 1 ) )
return true;
for ( int i = 0; i < 2; ++i )
if ( checkDiagonal( board, k, i ) )
return true;
return false;
}
int main() {
int t;
scanf( "%d", &t );
for ( int test = 0; test < t; ++test ) {
char board[ 4 ][ 10 ];
for ( int i = 0; i < 4; ++i )
scanf( "%s", board[ i ] );
if ( checkWin( board, 'X' ) )
printf( "Case #%d: X won\n", test + 1 );
else if ( checkWin( board, 'O' ) )
printf( "Case #%d: O won\n", test + 1 );
else if ( !checkFull( board ) )
printf( "Case #%d: Game has not completed\n", test + 1 );
else
printf( "Case #%d: Draw\n", test + 1 );
}
return 0;
}

Source code on gist.