fork download
copy 
  1. from collections import deque
  2.  
  3. # Define the possible connections for each pipe type
  4. pipe_connections = {
  5.     '═': {'left': (0, -1), 'right': (0, 1)},
  6.     '║': {'up': (-1, 0), 'down': (1, 0)},
  7.     '╔': {'right': (0, 1), 'down': (1, 0)},
  8.     '╗': {'left': (0, -1), 'down': (1, 0)},
  9.     '╚': {'right': (0, 1), 'up': (-1, 0)},
  10.     '╝': {'left': (0, -1), 'up': (-1, 0)},
  11.     '╠': {'right': (0, 1), 'down': (1, 0), 'up': (-1, 0)},
  12.     '╣': {'left': (0, -1), 'down': (1, 0), 'up': (-1, 0)},
  13.     '╦': {'left': (0, -1), 'right': (0, 1), 'down': (1, 0)},
  14.     '╩': {'left': (0, -1), 'right': (0, 1), 'up': (-1, 0)}
  15. }
  16.  
  17. # Define reverse connections for bidirectional checking
  18. reverse_directions = {
  19.     'left': 'right',
  20.     'right': 'left',
  21.     'up': 'down',
  22.     'down': 'up'
  23. }
  24.  
  25. # Helper function to get all valid neighbors based on pipe type and connectivity
  26. def get_neighbors(grid, row, col):
  27.     neighbors = []
  28.     cell = grid[row][col]
  29.     if cell in pipe_connections:
  30.         for direction, (dr, dc) in pipe_connections[cell].items():
  31.             nr, nc = row + dr, col + dc
  32.             if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
  33.                 neighbor_cell = grid[nr][nc]
  34.                 if neighbor_cell == '*' or neighbor_cell.isupper():
  35.                     neighbors.append((nr, nc))
  36.                 elif neighbor_cell in pipe_connections:
  37.                     if reverse_directions[direction] in pipe_connections[neighbor_cell]:
  38.                         neighbors.append((nr, nc))
  39.     return neighbors
  40.  
  41. def is_connected(grid, start):
  42.     rows, cols = len(grid), len(grid[0])
  43.     queue = deque([start])
  44.     visited = set([start])
  45.     connected_sinks = set()
  46.  
  47.     while queue:
  48.         r, c = queue.popleft()
  49.         for nr, nc in get_neighbors(grid, r, c):
  50.             if (nr, nc) not in visited:
  51.                 visited.add((nr, nc))
  52.                 queue.append((nr, nc))
  53.                 if grid[nr][nc].isupper():
  54.                     connected_sinks.add(grid[nr][nc])
  55.  
  56.     return connected_sinks
  57.  
  58. def find_connected_sinks(grid):
  59.     # Locate the source
  60.     start = None
  61.     for r in range(len(grid)):
  62.         for c in range(len(grid[0])):
  63.             if grid[r][c] == '*':
  64.                 start = (r, c)
  65.                 break
  66.         if start:
  67.             break
  68.  
  69.     if not start:
  70.         return set()  # No source found
  71.  
  72.     return is_connected(grid, start)
  73.  
  74. # Example usage
  75.  
Success #stdin #stdout 0.03s 9640KB
comments (?)
stdin
copy 
* 0 2
C 1 0
╠ 1 1
╣ 1 2
═ 2 1
╚ 3 0
╝ 3 1
╔ 3 2
═ 4 0
═ 4 2
B 5 0
A 5 2
stdout
copy 
Standard output is empty
https://ideone.com/YL6NJ0
language:
Python 3 (python  3.9.5)
created:
49 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!