Show problems as
Classic problem #3071MediumArrayHash TableMatrixCounting

Minimum Operations to Write the Letter Y on a Grid

Real-world version: Repainting a Board Into a Wye
Tracked in this browser only
Read Minimum Operations to Write the Letter Y on a Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A square board of odd side is given as grid, each cell holding 0, 1 or 2. One repaint changes a single cell to any of the three values.

The wye is the set of cells on the two diagonals running down from the top corners as far as the middle cell, together with the cells straight below the middle cell. Every other cell is outside the wye.

The board shows a wye when every cell of the wye holds one value, every cell outside holds one value, and those two values differ. Return the fewest repaints that leave the board showing a wye.

Examples

Example 1

Input
grid = [[1, 0, 1], [0, 1, 0], [0, 1, 0]]
Output
0

The wye holds the corners of the top row, the middle cell and the two cells below it, and those already read 1, 1, 1, 1, 1. Everything outside already reads 0, so the board already shows a wye.

Example 2

Input
grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Output
4

Every cell reads 0, so one of the two parts has to be repainted, and the wye is the smaller of the two.

Example 3

Input
grid = [[2, 0, 2], [1, 2, 1], [0, 1, 0]]
Output
3

Painting the wye 2 leaves three of its five cells to change, and painting everything else 1 leaves two of the four outside cells to change.

Constraints

  • 3 <= grid.length <= 49
  • grid.length == grid[i].length
  • grid.length is odd
  • 0 <= grid[i][j] <= 2

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_operations_to_write_y(grid: list[list[int]]) -> int:
Java
public int minimumOperationsToWriteY(int[][] grid)

More on the same topics