結果
| 問題 |
No.86 TVザッピング(2)
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:58:33 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,594 bytes |
| コンパイル時間 | 189 ms |
| コンパイル使用メモリ | 81,968 KB |
| 実行使用メモリ | 151,920 KB |
| 最終ジャッジ日時 | 2025-06-20 14:02:29 |
| 合計ジャッジ時間 | 8,118 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 6 WA * 1 TLE * 1 -- * 22 |
ソースコード
import sys
# Increase recursion depth limit for potentially deep paths.
# The maximum path length (number of moves) is T, which can be up to N*M = 100*100 = 10000.
# The recursion depth can reach T. Setting it slightly above the maximum possible T.
try:
sys.setrecursionlimit(10500)
except OverflowError: # Handle potential OS limits on stack size
# If setting a high limit fails, use a default reasonable limit or warn.
# This might cause RecursionError on large test cases if the limit is too low.
# Let's just let it fail if the system cannot handle it. The competitive programming environment usually allows high limits.
pass
def solve():
N, M = map(int, sys.stdin.readline().split())
A = [sys.stdin.readline().strip() for _ in range(N)]
# Find all available cells (marked with '.')
available_cells = []
for r in range(N):
for c in range(M):
if A[r][c] == '.':
available_cells.append((r, c))
# Total number of available cells
T = len(available_cells)
# Based on graph theory (Hamiltonian cycle on bipartite graph) and problem rules analysis:
# 1. The number of available cells T must be even.
# 2. Analysis showed T=2 is impossible due to turn constraints.
# Therefore, T must be even and T >= 4 for a cycle to possibly exist.
if T % 2 != 0 or T < 4:
print("NO")
return
# Precompute adjacency list for available cells for efficiency.
# adj maps cell coordinates (tuple) to a list of adjacent available cell coordinates.
adj = {}
for r_idx in range(N):
for c_idx in range(M):
if A[r_idx][c_idx] == '.':
curr_cell = (r_idx, c_idx)
adj[curr_cell] = []
# Check potential neighbors in 4 cardinal directions
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # Right, Left, Down, Up
nr, nc = r_idx + dr, c_idx + dc
# Check if neighbor is within grid boundaries and is an available cell '.'
if 0 <= nr < N and 0 <= nc < M and A[nr][nc] == '.':
adj[curr_cell].append((nr, nc))
# Keep track of visited cells for the current DFS path. Use a 2D list for potentially better performance than dict.
visited = [[False for _ in range(M)] for _ in range(N)]
# Global variables to store context about the start of the path, needed for cycle closure checks.
start_cell_global = None # Stores the coordinates (tuple) of the starting cell for the current DFS attempt
first_move_dir_global = None # Stores the direction (dr, dc tuple) of the first move (v0 -> v1)
# Helper function to calculate the direction vector (dr, dc) from one cell to an adjacent cell.
def get_dir(from_cell, to_cell):
return (to_cell[0] - from_cell[0], to_cell[1] - from_cell[1])
# Helper function to calculate the direction resulting from a 90-degree left turn.
def left_turn(dr, dc):
# Rotation logic: (dr, dc) rotated left 90 degrees becomes (-dc, dr).
return (-dc, dr)
# Helper function to check if `curr_dir` is a valid next direction after `prev_dir`
# according to the problem rule: "straight or left turn".
def check_turn(prev_dir, curr_dir):
# Check if move is straight
if curr_dir == prev_dir:
return True
# Check if move is a left turn
lt_dir = left_turn(prev_dir[0], prev_dir[1])
if curr_dir == lt_dir:
return True
# If neither, the move direction is invalid by the rules
return False
# Depth First Search function to explore paths and check for a valid cycle.
# Parameters:
# curr_cell: The current cell coordinates (tuple).
# prev_cell: The coordinates of the cell visited just before curr_cell (tuple).
# visited_count: The number of distinct available cells visited so far in the current path.
def dfs(curr_cell, prev_cell, visited_count):
curr_r, curr_c = curr_cell
# Determine the direction of the move that arrived at curr_cell.
curr_dir = get_dir(prev_cell, curr_cell)
# Base Case: If T cells have been visited, check if path can close into a valid cycle.
if visited_count == T:
# Need to check if moving from curr_cell back to start_cell_global is possible and valid.
# 1. Adjacency Check: Is start_cell_global adjacent to curr_cell?
# Use Manhattan distance for grid adjacency check.
if abs(curr_r - start_cell_global[0]) + abs(curr_c - start_cell_global[1]) != 1:
return False # Not adjacent, cannot form cycle.
# 2. Calculate Final Move Direction: Determine direction for the move back to start.
final_dir = get_dir(curr_cell, start_cell_global)
# 3. Final Move Turn Rule Check: Does the final move (v_{T-1} -> v_0) follow the turn rule based on the previous move (v_{T-2} -> v_{T-1})?
# The direction of the move v_{T-2} -> v_{T-1} is stored in curr_dir.
if not check_turn(curr_dir, final_dir):
return False
# 4. First Move Turn Rule Check (Cycle Consistency): Does the first move (v_0 -> v_1) follow the turn rule based on the final move (v_{T-1} -> v_0)?
# This ensures the turn rule holds across the cycle wrap-around.
if not check_turn(final_dir, first_move_dir_global):
return False
# If all checks pass, we have found a valid cycle satisfying all conditions.
return True
# Recursive Step: Explore possible next moves from curr_cell.
# Mark current cell as visited for this path exploration.
visited[curr_r][curr_c] = True
# Calculate the two possible next directions according to the rules: straight or left turn.
straight_dir = curr_dir
left_turn_dir = left_turn(curr_dir[0], curr_dir[1])
# Try moving Straight
next_cell_S = (curr_r + straight_dir[0], curr_c + straight_dir[1])
# Check if the cell is within bounds and is an available cell ('.')
if 0 <= next_cell_S[0] < N and 0 <= next_cell_S[1] < M and A[next_cell_S[0]][next_cell_S[1]] == '.':
# Check if the cell hasn't been visited yet in the current path
if not visited[next_cell_S[0]][next_cell_S[1]]:
# Recursively call DFS for the next cell
if dfs(next_cell_S, curr_cell, visited_count + 1):
# If recursive call found a solution, propagate True up the call stack.
return True
# If the target is the start cell, it must be the final move to close the cycle.
# This logic is implicitly handled by the base case check when visited_count reaches T.
# The `not visited` check correctly prevents revisiting start_cell_global prematurely.
# Try moving Left Turn
next_cell_L = (curr_r + left_turn_dir[0], curr_c + left_turn_dir[1])
# Check if the cell is valid
if 0 <= next_cell_L[0] < N and 0 <= next_cell_L[1] < M and A[next_cell_L[0]][next_cell_L[1]] == '.':
# Check if the cell hasn't been visited yet
if not visited[next_cell_L[0]][next_cell_L[1]]:
# Recurse
if dfs(next_cell_L, curr_cell, visited_count + 1):
return True
# Similar implicit handling if next_cell_L is the start cell.
# Backtrack: If no path found from curr_cell, unmark it as visited.
# This allows other paths to potentially use this cell.
visited[curr_r][curr_c] = False
# Return False indicating no solution found from this state downwards.
return False
# Main loop to initiate DFS search attempts.
# Try starting the path from each available cell.
for r_start, c_start in available_cells:
start_cell = (r_start, c_start)
# A starting cell must have at least one neighbor to start a path.
# adj check handles isolated '.' cells, although problem guarantees T>=2.
if start_cell not in adj or not adj[start_cell]: continue
# Try each neighbor of the start cell as the target of the first move.
for first_neighbor in adj[start_cell]:
# Reset the visited state tracker for each new DFS attempt.
for r_vis in range(N):
for c_vis in range(M):
visited[r_vis][c_vis] = False
# Set the global context variables for this specific DFS run.
start_cell_global = start_cell
first_move_dir_global = get_dir(start_cell, first_neighbor)
# Mark the starting cell as visited before initiating DFS.
visited[r_start][c_start] = True
# Start the DFS from the first neighbor.
# The initial path has length 1 (1 move), involves 2 cells (start and first neighbor).
# So, visited_count starts at 2.
if dfs(first_neighbor, start_cell, 2):
# If DFS returns True, a valid cycle path has been found.
print("YES")
return # Exit the function immediately.
# If the loops complete without finding any valid path from any start cell / first move combination.
print("NO")
# Call the main solve function to run the logic.
solve()