Flip Tool

from collections import deque

# Calculate the diameter of a tree
def find_diameter(graph):
    # BFS to find the farthest node and its distance
    def bfs(start):
        dist = [-1] * len(graph)  # Initialize the distance array, all nodes set to -1
        dist[start] = 0  # Set the starting node's distance to 0
        queue = deque([start])  # Initialize the queue
        farthest = start  # Initialize the farthest node as the starting node
        while queue:
            node = queue.popleft()  # Dequeue the front element
            for neighbor in graph[node]:  # Traverse adjacent nodes
                if dist[neighbor] == -1:  # If the neighbor has not been visited
                    dist[neighbor] = dist[node] + 1  # Update the distance
                    queue.append(neighbor)  # Enqueue the neighbor
                    if dist[neighbor] > dist[farthest]:  # Update the farthest node
                        farthest = neighbor
        return farthest, dist[farthest]  # Return the farthest node and its distance

    # Choose an arbitrary node as the starting point
    start, _ = bfs(0)
    # Find the farthest node from the starting point
    end, diameter = bfs(start)
    return diameter

# Main algorithm
def solve(R, C, image):
    # BFS to find 8-connected components, merging all connected pixels into one set as a supernode
    def bfs(start_i, start_j, color):
        component = []  # Store the current connected component
        queue = deque([(start_i, start_j)])  # Initialize the queue
        visited.add((start_i, start_j))  # Mark the pixel as visited

        while queue:
            i, j = queue.popleft()  # Dequeue the front element
            component.append((i, j))  # Add the pixel to the current connected component

            # Traverse in 8 directions
            for di, dj in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
                ni, nj = i + di, j + dj
                # Check boundary conditions and color match
                if 0 <= ni < R and 0 <= nj < C and image[ni][nj] == color and (ni, nj) not in visited:
                    queue.append((ni, nj))  # Enqueue the pixel
                    visited.add((ni, nj))  # Mark the pixel as visited

        return component

    visited = set()  # Set of visited pixels
    components = []  # List to store all connected components
    component_map = [[-1] * C for _ in range(R)]  # Map pixels to their connected component IDs
    # Traverse each pixel to find all 8-connected components
    for i in range(R):
        for j in range(C):
            if (i, j) not in visited:
                component = bfs(i, j, image[i][j])  # Find a connected component
                component_index = len(components)  # Index of the current connected component
                components.append(component)  # Add the component to the list
                for x, y in component:
                    component_map[x][y] = component_index  # Update the mapping

    # Build the connectivity between connected components
    graph = [set() for _ in range(len(components))]  # Initialize the graph
    for i in range(R):
        for j in range(C):
            current_component = component_map[i][j]  # Current pixel's connected component
            # Traverse in 8 directions
            for di, dj in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < R and 0 <= nj < C:
                    neighbor_component = component_map[ni][nj]  # Neighbor pixel's connected component
                    if neighbor_component != current_component:
                        graph[current_component].add(neighbor_component)  # Add an edge
                        graph[neighbor_component].add(current_component)  # Add an edge

    # Convert sets to lists
    graph = [list(neighbors) for neighbors in graph]
    # Find the diameter of the supergraph (which is guaranteed to be a tree)
    diameter = find_diameter(graph)
    return (diameter + 1) // 2  # Return the minimum number of flips

# Read input
R, C = map(int, input().split())
image = [input().strip() for _ in range(R)]

# Generate random data for debugging
import random
def generate_random_input(max_R=20, max_C=20):
    R = random.randint(1, max_R)  # Randomly generate the number of rows
    C = random.randint(1, max_C)  # Randomly generate the number of columns
    image = []
    for _ in range(R):
        row = ''.join(random.choice('.x') for _ in range(C))  # Randomly generate the image
        image.append(row)

    print(f"{R} {C}")
    for row in image:
        print(row)

    return R, C, image

# Use randomly generated input
# R, C, image = generate_random_input()

# Output the result
print(solve(R, C, image))