import sys
# Constants
MX = 10000
class Type:
def __init__(self, id=None, value=0):
self.id = id
self.value = value
def comp(a):
# Comparison function for sorting ranks
# Primary sort: descending order of value (using negative to achieve descending)
# Secondary sort: ascending order of id (in case of equal values)
# Useful for ranking components by size and then by identifier
return (-a.value, a.id)
def init(h, w):
# Initialize a list of Type objects with default values
# Creates an empty data structure of specified dimensions
# Useful for pre-allocating space for graph-related data structures
return [Type() for _ in range(h * w)]
def set_rank(ranks, c, r):
for rank in ranks:
if rank.id == c:
rank.value += r
return
new_rank = Type(id=c, value=r)
ranks.append(new_rank)
def dfs_visit(graph, a, b, h, w):
# Capturing the original color/type of the current cell before modification
temp_c = graph[a][b]
# label v as discovered
# Mark the current cell as 'visited' to prevent re-exploration and avoid infinite recursion
graph[a][b] = 'G'
# Directional movements represent the possible traversal directions
# These coordinates allow checking adjacent cells (left, up, right, down)
dr = [0, -1, 0, 1]
dc = [-1, 0, 1, 0]
# for all directed edges from v to w that are in G.adjacentEdges(v) do
# Iterate through all four possible adjacent directions
for i in range(4):
r = dr[i] + a
c = dc[i] + b
# if vertex w is not labeled as discovered then
# Check if the adjacent cell is within graph boundaries and of the same color/type
if (0 <= r < h and 0 <= c < w and
graph[r][c] == temp_c):
# recursively call DFS(G, w)
# Explore the connected component by recursively visiting adjacent cells
dfs_visit(graph, r, c, h, w)
# Mark the cell as completely explored to distinguish from undiscovered cells
graph[a][b] = 'B'
def dfs(graph, h, w):
# Initialize a list to store ranked components
ranks = []
# for all directed edges from v to w that are in G.adjacentEdges(v) do
# Traverse through entire graph to find and explore connected components
for i in range(h):
for j in range(w):
# if vertex w is not labeled as discovered then
# Check if the current cell hasn't been explored in previous DFS calls
if graph[i][j] not in ['G', 'B']:
# Assign initial rank to the newly discovered component
set_rank(ranks, graph[i][j], 1)
# recursively call DFS(G, w)
# Start DFS from this undiscovered cell to explore its entire component
dfs_visit(graph, i, j, h, w)
return ranks
def process_world(h, w, graph_input):
# Convert input to 2D list for easier manipulation
graph = [list(row) for row in graph_input]
# Perform depth-first search to identify and rank components
ranks = dfs(graph, h, w)
# Sort ranks in descending order of component size, with secondary sorting by component ID
ranks.sort(key=comp)
return ranks
test_cases = int(input())
cases = 0
for _ in range(test_cases):
h, w = map(int, input().split())
graph_input = [input() for _ in range(h)]
cases += 1
ranks = process_world(h, w, graph_input)
print(f"World #{cases}")
for rank in ranks:
print(f"{rank.id}: {rank.value}")
.jpg)
