Errich-Tac-Toe (Easy Version) (Codeforces 1450C1)
Tags: Math, constructive algorithms

The only difference between the easy and hard versions is that tokens of type O do not appear in the input of the easy version.Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces.In a Tic-Tac-Toe grid, there are $$$n$$$ rows and $$$n$$$ columns. Each cell of the grid is either empty or contains a token. There are two types of tokens: X and O. If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration.  The patterns in the first row are winning configurations. The patterns in the second row are draw configurations. In an operation, you can change an X to an O, or an O to an X. Let $$$k$$$ denote the total number of tokens in the grid. Your task is to make the grid a draw in at most $$$\lfloor \frac{k}{3}\rfloor$$$ (rounding down) operations.You are not required to minimize the number of operations.

Input: The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 300$$$) — the size of the grid.The following $$$n$$$ lines each contain a string of $$$n$$$ characters, denoting the initial grid. The character in the $$$i$$$-th row and $$$j$$$-th column is '.' if the cell is empty, or it is the type of token in the cell: 'X' or 'O'.It is guaranteed that not all cells are empty.In the easy version, the character 'O' does not appear in the input.The sum of $$$n$$$ across all test cases does not exceed $$$300$$$.

Output: For each test case, print the state of the grid after applying the operations.We have proof that a solution always exists. If there are multiple solutions, print any.

Note: In the first test case, there are initially three 'X' consecutive in the second row and the second column. By changing the middle token to 'O' we make the grid a draw, and we only changed $$$1\le \lfloor 5/3\rfloor$$$ token.In the second test case, we change only $$$9\le \lfloor 32/3\rfloor$$$ tokens, and there does not exist any three 'X' or 'O' consecutive in a row or column, so it is a draw.In the third test case, we change only $$$3\le \lfloor 12/3\rfloor$$$ tokens, and the resulting grid is a draw.

Sample Inputs:
3
3
.X.
XXX
.X.
6
XX.XXX
XXXXXX
XXX.XX
XXXXXX
XX.X.X
XXXXXX
5
XXX.X
.X..X
XXX.X
..X..
..X..

Sample Outputs:
.X.
XOX
.X.
XX.XXO
XOXXOX
OXX.XX
XOOXXO
XX.X.X
OXXOXX
XOX.X
.X..X
XXO.O
..X..
..X..

Solution (Python):
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def solve():
    for _ in range(inp()):
        n = inp()
        s = [list(input()) for _ in range(n)]
        count = [0, 0, 0]
        for i in range(n):
            for j in range(n):
                if s[i][j] == 'X':
                    count[(i + j) % 3] += 1
        mini = min(count)
        idx = count.index(mini)
        for i in range(n):
            for j in range(n):
                if s[i][j] == 'X' and (i + j) % 3 == idx:
                    s[i][j] = 'O'
        for string in s:
            print(''.join(string))
solve()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    ar = [[x for x in input()] for _ in range(n)]
    c = [0, 0, 0]
    for i in range(n):
        for j in range(n):
            if ar[i][j] == 'X':
                c[(i + j) % 3] += 1
    e = c.index(min(c))
    for i in range(n):
        for j in range(n):
            if ar[i][j] == 'X' and (i + j) % 3 == e:
                ar[i][j] = 'O'
    for e in ar:
        print(''.join(e))

Solution (Python):
def ticTackToe():
    t = int(input())
    for _ in range(t):
        n = int(input())
        grid = []
        for i in range(n):
            grid.append(list(input()))
        p0 = 0
        p1 = 0
        p2 = 0
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 'X':
                    if (i + j) % 3 == 0:
                        p0 += 1
                    elif (i + j) % 3 == 1:
                        p1 += 1
                    else:
                        p2 += 1
        parity = 0
        if p1 <= min(p2, p0):
            parity = 1
        elif p2 <= min(p1, p0):
            parity = 2
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 'X':
                    if (i + j) % 3 == parity:
                        grid[i][j] = 'O'
        for g in grid:
            print(''.join(g))
ticTackToe()