Apr 14, 2013
題目概述
給定一個圈圈叉叉的遊戲狀態,判斷給定的狀態屬於下列哪一種:
- 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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*============================================================================= | |
# 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.