結果
| 問題 |
No.348 カゴメカゴメ
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,815 bytes |
| コンパイル時間 | 457 ms |
| コンパイル使用メモリ | 82,652 KB |
| 実行使用メモリ | 326,884 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:34 |
| 合計ジャッジ時間 | 16,838 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 WA * 30 |
ソースコード
import sys
# Set recursion depth limit. This is necessary for deep hierarchies potentially formed by nested rings.
# The exact required depth is hard to predict, so a reasonably large value is chosen.
# If this value is too high for the system or contest environment, it might need adjustment.
try:
# Attempt to set a high recursion depth suitable for large grids (up to 1000x1000)
sys.setrecursionlimit(2000 * 1000) # Target potentially deep structures. Maybe too high for some systems.
except OverflowError:
# If the system limits prevent setting a very high value, fallback to smaller but still large values.
try:
sys.setrecursionlimit(30000)
except OverflowError:
try:
sys.setrecursionlimit(20000)
except OverflowError:
sys.setrecursionlimit(10000) # A common safe upper value in competitive programming
def solve():
N, M = map(int, sys.stdin.readline().split())
grid = [sys.stdin.readline().strip() for _ in range(N)]
# Pad the grid with '.' boundary. This simplifies boundary condition checks
# and helps define the exterior region consistently.
padded_N = N + 2
padded_M = M + 2
padded_grid = [['.' for _ in range(padded_M)] for _ in range(padded_N)]
x_cells = [] # Store coordinates of all 'x' cells for efficient iteration
for r in range(N):
for c in range(M):
padded_grid[r+1][c+1] = grid[r][c]
if grid[r][c] == 'x':
x_cells.append((r+1, c+1)) # Use padded coordinates (1-based indexing effectively)
# If there are no 'x' cells, the maximum strength is 0.
if not x_cells:
print(0)
return
# --- Step 1: Identify all rings and their strengths ---
visited_x = [[False for _ in range(padded_M)] for _ in range(padded_N)] # Track visited 'x' cells during tracing
rings = [] # List to store coordinates of cells for each ring
ring_strengths = [] # List to store the strength (number of 'x's) of each ring
# cell_to_ring_id = [[-1 for _ in range(padded_M)] for _ in range(padded_N)] # Optional: Map cell coord to its ring ID
ring_idx_counter = 0 # Assign a unique ID (0, 1, 2, ...) to each ring
# Define 8-connectivity directions (dx, dy) for neighbors
dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]
for start_r, start_c in x_cells:
if not visited_x[start_r][start_c]: # If this 'x' cell hasn't been visited, it's part of a new ring
current_ring_coords = [] # Store coordinates for the current ring being traced
# Trace the ring using iterative approach. Problem guarantees each 'x' has exactly two 'x' neighbors.
curr_r, curr_c = start_r, start_c
prev_r, prev_c = -1, -1 # Track previous cell to avoid backtracking immediately
# Find the first neighbor to start the walk along the ring
initial_neighbor_found = False
for i in range(8):
nr, nc = curr_r + dr[i], curr_c + dc[i]
# Check bounds and if neighbor is 'x'
if 0 <= nr < padded_N and 0 <= nc < padded_M and padded_grid[nr][nc] == 'x':
prev_r, prev_c = curr_r, curr_c # Update previous cell tracker
curr_r, curr_c = nr, nc # Move to the neighbor
initial_neighbor_found = True
break
if not initial_neighbor_found: continue # Should not happen given problem constraints
# Add the starting cell to the ring path and mark as visited
current_ring_coords.append((start_r, start_c))
visited_x[start_r][start_c] = True
# cell_to_ring_id[start_r][start_c] = ring_idx_counter
# Continue tracing the ring until we return to the start cell
while not (curr_r == start_r and curr_c == start_c):
# Add current cell to path and mark visited
current_ring_coords.append((curr_r, curr_c))
visited_x[curr_r][curr_c] = True
# cell_to_ring_id[curr_r][curr_c] = ring_idx_counter
# Find the next neighbor in the ring path (must be 'x' and not the previous cell)
next_found = False
for i in range(8):
next_r, next_c = curr_r + dr[i], curr_c + dc[i]
# Check bounds and cell type
if not (0 <= next_r < padded_N and 0 <= next_c < padded_M): continue
if padded_grid[next_r][next_c] != 'x': continue
# Ensure it's not the cell we just came from
if next_r == prev_r and next_c == prev_c: continue
# Move to the next cell
prev_r, prev_c = curr_r, curr_c
curr_r, curr_c = next_r, next_c
next_found = True
break # Found the unique next cell in path
# Store the completed ring and its strength
rings.append(current_ring_coords)
ring_strengths.append(len(current_ring_coords))
ring_idx_counter += 1
num_rings = len(rings)
# If somehow no rings were found (e.g. invalid input structures, though problem guarantees valid ones)
if num_rings == 0:
print(0)
return
# --- Step 2: Identify connected components of '.' cells ---
component_id = [[-1 for _ in range(padded_M)] for _ in range(padded_N)] # Assign component ID to each '.' cell
comp_idx_counter = 0 # Counter for component IDs
# Use BFS to find connected components. Start with Component 0 (C0), the exterior region.
q_bfs = [(0,0)] # Start BFS from a boundary cell (0,0) guaranteed to be '.' due to padding
component_id[0][0] = comp_idx_counter
head_bfs = 0
while head_bfs < len(q_bfs):
r, c = q_bfs[head_bfs]; head_bfs += 1
# Explore 4-direction neighbors
for dr_4, dc_4 in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr_4, c + dc_4
# Check bounds, if it's '.' cell, and if unvisited
if 0 <= nr < padded_N and 0 <= nc < padded_M and padded_grid[nr][nc] == '.' and component_id[nr][nc] == -1:
component_id[nr][nc] = comp_idx_counter
q_bfs.append((nr, nc))
comp_idx_counter += 1 # Increment for next component ID
# Find any remaining interior components
for r in range(padded_N):
for c in range(padded_M):
if padded_grid[r][c] == '.' and component_id[r][c] == -1: # Found an unvisited '.' cell
# Start BFS for new component
q_bfs = [(r, c)]; component_id[r][c] = comp_idx_counter; head_bfs = 0
while head_bfs < len(q_bfs):
curr_r, curr_c = q_bfs[head_bfs]; head_bfs += 1
for dr_4, dc_4 in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = curr_r + dr_4, curr_c + dc_4
if 0 <= nr < padded_N and 0 <= nc < padded_M and padded_grid[nr][nc] == '.' and component_id[nr][nc] == -1:
component_id[nr][nc] = comp_idx_counter
q_bfs.append((nr, nc))
comp_idx_counter += 1 # Increment for next component ID
num_components = comp_idx_counter # Total number of '.' components
initial_num_components = num_components # Store original count before potentially adding dummy components
# --- Step 3: Build Component Graph and Ring Hierarchy ---
# Map rings to the pair of components they separate & Build Component Graph Adjacency List
ring_to_components = {} # Stores pair [comp_id1, comp_id2] for each ring_id
adjComp = {} # Adjacency list for component graph: comp_id -> list of (neighbor_comp_id, ring_id)
for comp_id in range(num_components): adjComp[comp_id] = [] # Initialize empty lists for all components
for ring_id in range(num_rings):
adj_comps = set() # Collect unique component IDs adjacent to this ring
# Check 4-neighbors of each 'x' in the ring
for r, c in rings[ring_id]:
for dr_4, dc_4 in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr_4, c + dc_4
if 0 <= nr < padded_N and 0 <= nc < padded_M and padded_grid[nr][nc] == '.':
comp_id_neighbor = component_id[nr][nc]
if comp_id_neighbor != -1: # Make sure it's a valid component ID
adj_comps.add(comp_id_neighbor)
# Process based on number of adjacent components found
if len(adj_comps) == 2: # Standard case: ring separates two components
c1, c2 = list(adj_comps)
ring_to_components[ring_id] = [c1, c2]
# Add edges to component graph adjacency list
if c1 not in adjComp: adjComp[c1] = [] # Ensure list exists
if c2 not in adjComp: adjComp[c2] = []
adjComp[c1].append((c2, ring_id))
adjComp[c2].append((c1, ring_id))
elif len(adj_comps) == 1: # Special case: Ring adjacent only to one component
comp = list(adj_comps)[0]
if comp == 0: # If that component is C0 (exterior)
# Create a dummy component to represent the "inside" region for structural consistency
dummy_comp_id = num_components
ring_to_components[ring_id] = [0, dummy_comp_id]
# Add edge between C0 and the dummy component in the graph
if 0 not in adjComp: adjComp[0] = [] # Should already exist but check just in case
adjComp[0].append((dummy_comp_id, ring_id))
# Also add dummy component node and back edge
if dummy_comp_id not in adjComp: adjComp[dummy_comp_id] = []
adjComp[dummy_comp_id].append((0, ring_id))
num_components += 1 # Increment total component count for this new dummy node
# Else: adjacent to only one *interior* component? This case is unexpected based on problem statement.
# Determine parent-child relationships between components via BFS from C0
ParentComp = [-1] * num_components # Store parent component ID for each component
CompEdgeRing = {} # Map tuple (parent_comp, child_comp) -> ring_id separating them
q_bfs = [0]; visited_comp = {0}; ParentComp[0] = -2 # Mark C0 as root (-2 to distinguish from no parent -1)
head_bfs = 0
while head_bfs < len(q_bfs):
curr_comp = q_bfs[head_bfs]; head_bfs += 1
# Explore neighbors in the component graph
if curr_comp in adjComp:
for neighbor_comp, ring_id in adjComp[curr_comp]:
if neighbor_comp not in visited_comp:
visited_comp.add(neighbor_comp)
ParentComp[neighbor_comp] = curr_comp # Record parent
# Store the ring associated with the directed edge (parent -> child)
CompEdgeRing[(curr_comp, neighbor_comp)] = ring_id
q_bfs.append(neighbor_comp) # Add child to queue
# Construct the Ring Hierarchy Tree using an adjacency list
adjRing = [[] for _ in range(num_rings + 1)] # Adjacency list for rings, +1 for Virtual Root
VIRTUAL_ROOT = num_rings # Use index `num_rings` as the virtual root ID
for ring_id in range(num_rings):
if ring_id not in ring_to_components: continue # Skip if ring data missing
c1, c2 = ring_to_components[ring_id]
parent_c = -1 # Component closer to C0 (exterior)
# Determine which component is the parent based on the BFS tree structure
# ParentComp[x] stores the component from which x was visited in BFS from C0
if c1 < len(ParentComp) and ParentComp[c1] == c2: parent_c = c2
elif c2 < len(ParentComp) and ParentComp[c2] == c1: parent_c = c1
# Handle cases involving C0 or dummy components (children of C0)
# Need to ensure indices are valid before accessing ParentComp
elif c1 == 0 and c2 < len(ParentComp) and ParentComp[c2] == 0: parent_c = 0
elif c2 == 0 and c1 < len(ParentComp) and ParentComp[c1] == 0: parent_c = 0
if parent_c == -1 : continue # Error or unexpected structure
# Determine the parent ring ID based on the component hierarchy
if parent_c == 0: # If the parent component is C0, this ring is a top-level ring
ParentRingID = VIRTUAL_ROOT
else:
# Find the ring connecting parent_c to its parent (grandparent_c)
grandparent_c = ParentComp[parent_c]
# Look up the ring ID using the stored map CompEdgeRing
ParentRingID = CompEdgeRing.get((grandparent_c, parent_c), -1)
if ParentRingID == -1: continue # Error finding parent ring ID
# Add edge (ParentRingID -> ring_id) to the ring hierarchy tree
adjRing[ParentRingID].append(ring_id)
# --- Step 4: Dynamic Programming on the Ring Hierarchy Tree ---
dp_memo = {} # Memoization table for DP states: {ring_id: (dp0, dp1)}
# Recursive DP function
# Computes max strength for subtree rooted at ring `u`
# Returns tuple: (max strength NOT using ring u, max strength USING ring u)
def dfs_dp(u):
# Check memoization table
state = dp_memo.get(u)
if state is not None: return state
# Base case calculation / initialization for node u
dp0 = 0 # Max strength if ring u is NOT used
dp1 = 0 # Max strength if ring u IS used
# If u is a real ring (not virtual root), its strength contributes if used (dp1)
if u != VIRTUAL_ROOT:
dp1 = ring_strengths[u]
# Aggregate results from children subtrees
for v in adjRing[u]: # Iterate over children rings v of ring u
res_v0, res_v1 = dfs_dp(v) # Recursively get DP results for child v
# If u is NOT used, we can choose the best option for child v (use or not use)
dp0 += max(res_v0, res_v1)
# If u IS used, we CANNOT use its immediate child v (due to problem constraint)
dp1 += res_v0
# Store result in memoization table and return
dp_memo[u] = (dp0, dp1)
return dp0, dp1
# Calculate the final answer by calling DP starting from the virtual root.
# The virtual root represents the state outside all top-level rings.
# Since it's not a real ring, we can't "use" it. The answer is its dp0 value.
final_res0, _ = dfs_dp(VIRTUAL_ROOT)
print(final_res0)
solve()