結果
問題 | No.424 立体迷路 |
ユーザー |
|
提出日時 | 2016-09-22 22:44:05 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,672 bytes |
コンパイル時間 | 229 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-07-05 07:02:04 |
合計ジャッジ時間 | 1,783 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
class DisjointSet(object): def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n self.num = n # number of disjoint sets def union(self, x, y): self._link(self.find_set(x), self.find_set(y)) def _link(self, x, y): if x == y: return self.num -= 1 if self.rank[x] > self.rank[y]: self.parent[y] = x else: self.parent[x] = y if self.rank[x] == self.rank[y]: self.rank[y] += 1 def find_set(self, x): xp = self.parent[x] if xp != x: self.parent[x] = self.find_set(xp) return self.parent[x] def read_data(): h, w = map(int, input().split()) sx, sy, gx, gy = map(int, input().split()) bs = [] for _ in range(h): b = input() bs.append(list(map(int, b))) return h, w, sx - 1, sy - 1, gx - 1, gy - 1, bs def solve(h, w, sx, sy, gx, gy, bs): hw = h * w ds = DisjointSet(hw) for x in range(h): for y in range(w): pos = x * w + y b = bs[x][y] if x > 0 and abs(bs[x-1][y] - b) <= 1: ds.union(pos, pos - w) if y > 0 and abs(bs[x][y-1] - b) <= 1: ds.union(pos, pos - 1) if x > 1 and bs[x-2][y] == b and bs[x-1][y] < b: ds.union(pos, pos - w * 2) if y > 1 and bs[x][y-2] == b and bs[x][y-1] < b: ds.union(pos, pos - 2) s = sx * w + sy g = gx * w + gy if ds.find_set(s) == ds.find_set(g): print('YES') else: print('NO') param = read_data() solve(*param)