Codeforces #301 Div2 C: Ice Cave

1度Hackされてしまった。

問題

n×m(n,m ≦ 500)の洞窟の地図が与えられる。洞窟の床は氷の板からできており、各マスはひびのない床かひびの入った床のどちらかである。ひびのない床に移動すると床にひびが入り、ひびの入った床に移動すると床が割れて下のフロアに落ちてしまう。あるマスからは隣接するマスへ移動できる（同じマスでジャンプはできないとする）。スタートの位置とゴールの位置を与えられる。スタートのマスはすでにひびが入っているとする。またスタートとゴールは同じ位置である場合もある。ゴールのマスから下のフロアに落ちる事ができるかどうかを答えよ。

解法

まず、スタートのマスから途中ひびの入ったマスを通らずにゴールのマスに移動できることを確認する必要がある。これはDFSで判定できる。
そのあとスタートマスとゴールのマスの位置関係とひびの有無によって場合分けする。

ゴールのマスがスタートマスと同じ場合
ゴールのマスがスタートマスと隣接する場合
ゴールのマスがスタートマスと離れている場合

1の場合、一度隣接するマスに移動してからスタートマスに戻る必要があるので、隣接するマスにひびのないものがあれば条件を満たす。
2の場合、ゴールのマスにひびが入っているならそのまま移動すればいい。そうでなければゴールのマスに隣接するひびの無いマスがあれば条件を満たす。 3の場合、ゴールのマスにひびが入っているならそのまま移動すればいい。そうでなければゴールのマスに隣接するひびの無いマスが2つ以上あれば条件を満たす。ゴールのマスに移動するときに1度踏むマスとゴールのマスを2回踏むために経由するマスが必要だからである。

以下のコードではBFSしているようにみえるがキューに加えた座標から探索をしているのでDFSとなる。

drc = zip([0, 1, 0, -1], [1, 0, -1, 0])
n, m = map(int, raw_input().split())
C = [list(raw_input()) for i in xrange(n)]
r1, c1 = map(int, raw_input().split())
r1 -= 1; c1 -= 1
r2, c2 = map(int, raw_input().split())
r2 -= 1; c2 -= 1

que = [[r1, c1]]
visited = [[False] * m for i in xrange(n)]
while que:
    r, c = que.pop()
    if (r, c) == (r2, c2):
        break
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < m and ((nr, nc) == (r2, c2) or C[nr][nc] == "."):
            if visited[nr][nc]: continue
            visited[nr][nc] = True
            que.append([nr, nc])
else:
    print "NO"
    exit()

#隣接するひびのないマスを数える
cnt = 0
for dr, dc in drc:
    nr, nc = r2 + dr, c2 + dc
    if 0 <= nr < n and 0 <= nc < m and C[nr][nc] == ".":
       cnt += 1

dist = abs(r1 - r2) + abs(c1 - c2)
if dist == 0 and cnt >= 1:
    print "YES"
elif dist == 1 and (C[r2][c2] == "X" or cnt >= 1):
    print "YES"
elif dist > 1 and (C[r2][c2] == "X" or cnt >= 2):
    print "YES"
else:
    print "NO"