Phân tích: Tic-Tac-Toe-Tomek

Trong bài toán này, bạn phải phân loại trạng thái của một trò chơi Tic-Tac-Toe có một chút biến tấu. Bảng có kích thước \(4 \times 4\) và một ký hiệu bổ sung có thể xuất hiện trên bảng - chữ "T", mà cả hai người chơi đều có thể sử dụng để giành chiến thắng.

Lưu ý rằng mô tả bài toán đảm bảo dữ liệu vào sẽ luôn mô tả một bảng được tạo ra bởi một chuỗi các nước đi đúng quy tắc. Vì trò chơi kết thúc khi một người chơi thắng, điều này đảm bảo rằng chỉ có tối đa một người chơi có thể có bốn ký hiệu (hoặc 3 ký hiệu và một chữ T) trên một hàng/cột/đường chéo hoàn chỉnh.

Do đó, cách đơn giản nhất để kiểm tra xem một người chơi, ví dụ "X", có thắng hay không là kiểm tra tất cả các hàng, cột và đường chéo xem chúng có chỉ chứa các ký hiệu "T" và "X" hay không. Đừng quên kiểm tra cả hai đường chéo! Nếu có một hàng, cột hoặc đường chéo không chứa ký tự "." hoặc "O", chúng ta biết rằng X thắng. Tương tự, nếu có một hàng, cột hoặc đường chéo không chứa "X" hoặc ".", O thắng.

Nếu không có người chơi nào thắng, chúng ta chỉ cần phân biệt giữa kết quả hòa và trò chơi chưa kết thúc. Điều này tương đối đơn giản - nếu bảng chứa dù chỉ một ký tự ".", trò chơi chưa hoàn thành; ngược lại, đó là một trận hòa.

Lưu ý rằng các giải pháp của bạn được kiểm tra tự động bằng chương trình. Điều này có nghĩa là đầu ra của bạn phải khớp chính xác với đặc tả. Một số thí sinh đã gặp vấn đề do trả về "O Won" thay vì "O won" hoặc "The game has not been completed" thay vì "Game has not completed". Trong một cuộc thi lập trình, việc tuân thủ chính xác đặc tả đầu ra là rất quan trọng.

Cách cài đặt

Dưới đây là một giải pháp hoàn chỉnh bằng Python để tham khảo:

import sys

def solve(b):
  for c in ['X', 'O']:
    wind1 = True
    wind2 = True
    for x in range(4):
      winh = True
      winv = True
      for y in range(4):
        if b[y][x]!=c and b[y][x]!='T': winv = False
        if b[x][y]!=c and b[x][y]!='T': winh = False
      if winh or winv: return c + ' won'
      if b[x][x]!=c and b[x][x]!='T': wind1 = False
      if b[3-x][x]!=c and b[3-x][x]!='T': wind2 = False
    if wind1 or wind2: return c + ' won'

  for x in range(4):
    for y in range(4):
      if b[y][x]=='.': return 'Game has not completed'

  return 'Draw'


numcases = int(sys.stdin.readline())
for casenum in range(1,numcases+1):
  board = []
  for i in range(0,5):
    board.append(sys.stdin.readline().strip())
  print 'Case #' + repr(casenum) + ': ' + solve(board)

Độ phức tạp

Với mỗi bộ thử nghiệm, chúng ta kiểm tra 4 hàng, 4 cột và 2 đường chéo. Mỗi lần kiểm tra mất \(O(N)\) với \(N=4\). Tổng cộng có \(T\) bộ thử nghiệm, vì vậy độ phức tạp thời gian là \(O(T \times N)\), rất hiệu quả cho các giới hạn đã cho.

Dựa trên phân tích chính thức của Google Code Jam.