Paint a Y on the Board

Medium

You are given a square board board of odd size n × n; every cell holds a colour 0, 1 or 2. The letter Y on the board is made of three segments: - the diagonal from the top-left corner to the centre cell; - the diagonal from the top-right corner to the centre cell; - the vertical line from the centre cell down to the bottom edge. The Y counts as drawn when all its cells share one colour, all remaining cells share one colour too, and those two colours differ. In one action you can repaint any cell to 0, 1 or 2. Return the fewest actions after which the board shows the Y.

Example 1

board=[[2, 0, 2], [0, 2, 0], [0, 2, 0]] → 0

The Y is already there: its cells hold 2 and every other cell holds 0.

Example 2

board=[[1, 1, 1], [1, 1, 1], [1, 1, 1]] → 4

Keep the Y as 1s and repaint the four cells outside it, say to 0.

Example 3

board=[[0, 1, 2, 1, 0], [1, 0, 1, 0, 1], [2, 1, 0, 2, 1], [1, 1, 0, 1, 2], [2, 1, 1, 1, 1]] → 6

Constraints

3 ≤ n ≤ 49, n is odd
len(board) = len(board[i]) = n
board[i][j] ∈ {0, 1, 2}

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Counting Matrix

Similar problems

A Value Shared by Every Row Medium Primes Along Grid Rays Medium Sudoku Board Without Clashes Medium Zero Out the Crosses Medium More Than a Third of the Votes Medium

Input

board=[[2, 0, 2], [0, 2, 0], [0, 2, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.