Moshi Mosh !!!

code Herei

You’re given an NXM grid where each cell has an initial color. A stranger set is a group of cells that:

1. All share the same color.
2. No two cells in the set share a side (cells can touch diagonally but not edge-to-edge).

In a single step, you can choose any such stranger set and repaint all its cells in any other color. The objective is to make all cells the same color using the fewest steps.

Key Insight

For each color(c):

• If no pair of adjacent cells has color(c), you can repaint all of those cells in 1 step. (They’re already pairwise strangers.)
• If at least one pair of adjacent cells has color color(c), you need 2 steps to repaint all cells of that color. (Because you can split the connected component into two “stranger” groups.)

Hence, define for each color(c):

• color(c) = 0 if (c) does not appear in the grid.
• color(c) = 1 if (c) appears, but never in two adjacent cells.
• color(c) = 2 if (c) appears and there is at least one pair of adjacent cells color(c).

Choosing the Final Color

• Let S be the sum of color(c) over every color c that appears.
  • In code, this is computed as sum(has_color ) + sum(adj_found), where has_color [c] is 1 if c appears, and adj_found[c] is 1 if c has adjacent cells.
• If you select some color C* as the final color, you do not need to repaint cells already in C*.
• The minimum steps required to unify the grid into a single color is:

result = S - max(cost(c))

In the code, max(cost(c)) = 1 + max(adj_found[c]). Hence, the final result is:

result = (sum(has_color ) + sum(adj_found)) - 1 - max(adj_found)

Complexity Analysis:

• Time Complexity: O(n*m):

  • O(n*m) to read the grid and determine adjacent cells.
  • O(n*m) to compute costs and find the maximum cost.

• Space Complexity: O(n*m):

  • We store the entire grid n*m elements.
  • We also maintain two arrays of size (n*m) + 1 to track which colors appear and whether they have adjacent cells.

import sys 
input = sys.stdin.readline 

def solve():
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for i in range(n)]
    has_color = [0] * (n * m + 1)
    adj_found= [0] * (n * m + 1)

    for i in range(n):
        for j in range(m):
            has_color[grid[i][j]] = 1

            if i + 1 < n and grid[i][j] == grid[i + 1][j]:
                adj_found[grid[i][j]] = 1
            if j + 1 < m and grid[i][j] == grid[i][j + 1]:
                adj_found[grid[i][j]] = 1

    print(sum(has_color) + sum(adj_found) - 1 - max(adj_found))

if __name__ == '__main__':
    for _ in range(int(input())):
        solve()