Submission #24709890

---

Source Code Expand

import sys, copy
from collections import defaultdict, deque

g_counter = 0
group = defaultdict(int)
group_parent = defaultdict(int)

def create_group(r, c):
  global group, group_parent, g_counter
  g_counter += 1
  group[(r, c)] = g_counter
  group_parent[g_counter] = g_counter # self-point

def set_group(r, c, g):
  global group
  group[(r, c)] = g

def get_group(r, c):
  global group, group_parent
  p = group[(r, c)]
  if p == 0:
    return 0
  while group_parent[p] != p:
    p = group_parent[p]
  return p

def merge_group(p1, p2):
  global group_parent
  group_parent[p2] = group_parent[p1]

####

def add_link(r, c):
  global node, H, W
  node[r][c] = 1
  join = False
  for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    r2, c2 = r + dr, c + dc
    if 1 <= r2 <= H and 1 <= c2 <= W:
      if node[r2][c2] == 1:
        join = True
        g1 = get_group(r, c)
        g2 = get_group(r2, c2)
        if g1 == 0:
          set_group(r, c, g2)
        else:
          merge_group(g1, g2)
  if not join:
    create_group(r, c)

def search(r1, c1, r2, c2):
  global node, H, W
  if node[r1][c1] == 0 or node[r2][c2] == 0:
    return 'No'
  g1 = get_group(r1, c1)
  g2 = get_group(r2, c2)
  if g1 == g2:
    return 'Yes'
  else:
    return 'No'

def main(f):
  global node, H, W
  H, W = map(int, f.readline().split())
  node = [[0] * (W+1) for _ in range(H+1)]

  Q = int(f.readline())
  for _ in range(Q):
    tmp = list(map(int, f.readline().split()))
    if tmp[0] == 1:
      _, r, c = tmp
      add_link(r, c)
    else:
      _, r1, c1, r2, c2 = tmp
      print(search(r1, c1, r2, c2))

main(sys.stdin)

Submission Info

Judge Result