package main

import (
	"fmt"
)

func solve(board [][]byte) {
	height := len(board)
	if height == 0 {
		return
	}
	width := len(board[0])
	type Grid struct {
		X int
		Y int
	}
	flipMap := make(map[Grid]bool, 0)
	stack := make([]Grid, 0)
	for y := 0; y < height; y++ {
		for x := 0; x < width; x++ {
			if (x == 0 || x == width-1 || y == 0 || y == height-1) &&
				board[y][x] == 'O' {
				flipMap[Grid{x, y}] = true
				stack = append(stack, Grid{x, y})
			}
		}
	}
	for len(stack) != 0 {
		length := len(stack)
		grid := stack[length-1] // Pop top grid
		stack = stack[:length-1]
		if grid.X > 0 &&
			!flipMap[Grid{grid.X - 1, grid.Y}] && // If left grid's not visited
			board[grid.Y][grid.X-1] == 'O' {
			flipMap[Grid{grid.X - 1, grid.Y}] = true
			stack = append(stack, Grid{grid.X - 1, grid.Y})
		}
		if grid.X < width-1 &&
			!flipMap[Grid{grid.X + 1, grid.Y}] && // ...Right grid
			board[grid.Y][grid.X+1] == 'O' {
			flipMap[Grid{grid.X + 1, grid.Y}] = true
			stack = append(stack, Grid{grid.X + 1, grid.Y})
		}
		if grid.Y > 0 &&
			!flipMap[Grid{grid.X, grid.Y - 1}] && // ...Up
			board[grid.Y-1][grid.X] == 'O' {
			flipMap[Grid{grid.X, grid.Y - 1}] = true
			stack = append(stack, Grid{grid.X, grid.Y - 1})
		}
		if grid.Y < height-1 &&
			!flipMap[Grid{grid.X, grid.Y + 1}] && //...Down
			board[grid.Y+1][grid.X] == 'O' {
			flipMap[Grid{grid.X, grid.Y + 1}] = true
			stack = append(stack, Grid{grid.X, grid.Y + 1})
		}
	}
	for y := 0; y < height; y++ {
		for x := 0; x < width; x++ {
			if !flipMap[Grid{x, y}] && board[y][x] == 'O' {
				board[y][x] = 'X'
			}
		}
	}
}

func printBoard(board [][]byte) {
	for _, row := range board {
		for _, val := range row {
			fmt.Printf("%c ", val)
		}
		println()
	}
}

// func main() {
// 	b1 := [][]byte{
// 		{'X', 'X', 'X', 'X'},
// 		{'X', 'O', 'X', 'X'},
// 		{'X', 'X', 'O', 'X'},
// 		{'X', 'X', 'O', 'X'}}
// 	solve(b1)
// 	printBoard(b1)
// }