提出 #76871380

---

ソースコード 拡げる

import sys
from collections import deque
import time

def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    grid = [input().strip() for _ in range(N)]

    door_h = [[-1] * N for _ in range(N - 1)]
    door_v = [[-1] * (N - 1) for _ in range(N)]
    switch = [[-1] * N for _ in range(N)]
    switch_pos = [None] * K
    used_switch = [False] * K
    doors_placed = 0

    def is_open(g, mask):
        if g == -1:
            return True
        k = g // 2
        return ((mask >> k) & 1) == (g & 1)

    # 完全BFS（Tを返す）
    def calc_T():
        INF = -1
        total = N * N
        size = (1 << K) * total
        dist = [INF] * size
        dist[0] = 0
        q = deque([0])
        while q:
            idx = q.popleft()
            d = dist[idx]
            mask = idx // total
            pos = idx % total
            i = pos // N
            j = pos % N
            if i == N - 1 and j == N - 1:
                return d
            for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
                ni, nj = i + di, j + dj
                if not (0 <= ni < N and 0 <= nj < N):
                    continue
                if grid[ni][nj] == '#':
                    continue
                if di == 1:
                    g = door_h[i][j]
                elif di == -1:
                    g = door_h[ni][nj]
                elif dj == 1:
                    g = door_v[i][j]
                else:
                    g = door_v[ni][nj]
                if not is_open(g, mask):
                    continue
                nidx = mask * total + ni * N + nj
                if dist[nidx] == INF:
                    dist[nidx] = d + 1
                    q.append(nidx)
            s = switch[i][j]
            if s != -1:
                nmask = mask ^ (1 << s)
                nidx = nmask * total + i * N + j
                if dist[nidx] == INF:
                    dist[nidx] = d + 1
                    q.append(nidx)
        return 0

    # 経路復元つきBFS
    def calc_T_with_path():
        INF = -1
        total = N * N
        size = (1 << K) * total
        dist = [INF] * size
        prev = [(-1, -1, -1)] * size
        dist[0] = 0
        q = deque([0])
        while q:
            idx = q.popleft()
            d = dist[idx]
            mask = idx // total
            pos = idx % total
            i = pos // N
            j = pos % N
            if i == N - 1 and j == N - 1:
                path = []
                cur = idx
                while cur != -1:
                    cm = cur // total
                    cp = cur % total
                    ci = cp // N
                    cj = cp % N
                    path.append((cm, ci, cj))
                    p = prev[cur]
                    if p[0] == -1:
                        break
                    cur = p[0] * total + p[1] * N + p[2]
                path.reverse()
                return d, path
            for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
                ni, nj = i + di, j + dj
                if not (0 <= ni < N and 0 <= nj < N):
                    continue
                if grid[ni][nj] == '#':
                    continue
                if di == 1:
                    g = door_h[i][j]
                elif di == -1:
                    g = door_h[ni][nj]
                elif dj == 1:
                    g = door_v[i][j]
                else:
                    g = door_v[ni][nj]
                if not is_open(g, mask):
                    continue
                nidx = mask * total + ni * N + nj
                if dist[nidx] == INF:
                    dist[nidx] = d + 1
                    prev[nidx] = (mask, i, j)
                    q.append(nidx)
            s = switch[i][j]
            if s != -1:
                nmask = mask ^ (1 << s)
                nidx = nmask * total + i * N + j
                if dist[nidx] == INF:
                    dist[nidx] = d + 1
                    prev[nidx] = (mask, i, j)
                    q.append(nidx)
        return 0, []

    # 固定マスクの到達可能範囲（スイッチ操作なし）
    def bfs_reachable(start_mask, start_i, start_j, blocked_edge=None):
        dist = [[-1] * N for _ in range(N)]
        dist[start_i][start_j] = 0
        q = deque([(start_i, start_j)])
        while q:
            i, j = q.popleft()
            d = dist[i][j]
            for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
                ni, nj = i + di, j + dj
                if not (0 <= ni < N and 0 <= nj < N):
                    continue
                if grid[ni][nj] == '#':
                    continue
                if blocked_edge:
                    bi1, bj1, bi2, bj2 = blocked_edge
                    if (i==bi1 and j==bj1 and ni==bi2 and nj==bj2) or (i==bi2 and j==bj2 and ni==bi1 and nj==bj1):
                        continue
                if di == 1:
                    g = door_h[i][j]
                elif di == -1:
                    g = door_h[ni][nj]
                elif dj == 1:
                    g = door_v[i][j]
                else:
                    g = door_v[ni][nj]
                if not is_open(g, start_mask):
                    continue
                if dist[ni][nj] == -1:
                    dist[ni][nj] = d + 1
                    q.append((ni, nj))
        return dist

    start_time = time.time()
    TIME_LIMIT = 1.8  # 安全マージン

    # ----- メイン貪欲 -----
    current_T, current_path = calc_T_with_path()

    for k in range(K):
        if time.time() - start_time > TIME_LIMIT:
            break
        improved = True
        while improved and doors_placed < M:
            if time.time() - start_time > TIME_LIMIT:
                break
            if not current_path:
                break

            # 経路上の辺を列挙（最大50本）
            edges = []
            prev = current_path[0]
            for state in current_path[1:]:
                if state[1] != prev[1] or state[2] != prev[2]:
                    if state[1] == prev[1]:  # 横移動
                        jj = min(state[2], prev[2])
                        edges.append(('h', prev[1], jj, prev[0], prev[1], prev[2]))
                    else:  # 縦移動
                        ii = min(state[1], prev[1])
                        edges.append(('v', ii, prev[2], prev[0], prev[1], prev[2]))
                prev = state

            best_gain = 0
            best_door = None
            best_sw_pos = None

            seen = set()
            for edge in edges[:50]:  # 最初の50本だけ試す
                typ, ei, ej, emask, fi, fj = edge
                if typ == 'v':
                    if door_h[ei][ej] != -1:
                        continue
                    key = ('v', ei, ej)
                    blocked = (ei, ej, ei+1, ej)
                else:
                    if door_v[ei][ej] != -1:
                        continue
                    key = ('h', ei, ej)
                    blocked = (ei, ej, ei, ej+1)
                if key in seen:
                    continue
                seen.add(key)

                # スイッチ位置候補（最遠の空きマス）
                reach = bfs_reachable(emask, fi, fj, blocked)
                cand_sw = None
                max_d = -1
                for si in range(N):
                    for sj in range(N):
                        if reach[si][sj] != -1 and switch[si][sj] == -1 and grid[si][sj] == '.':
                            d = reach[si][sj]
                            if d > max_d:
                                max_d = d
                                cand_sw = (si, sj)
                if cand_sw is None:
                    continue

                # 仮設置
                if typ == 'v':
                    door_h[ei][ej] = 2 * k + 1
                else:
                    door_v[ei][ej] = 2 * k + 1
                si, sj = cand_sw
                old_sw_val = switch[si][sj]
                switch[si][sj] = k
                if not used_switch[k]:
                    # 未使用ならスイッチ位置を仮更新
                    old_sw_pos = switch_pos[k]
                    old_used = used_switch[k]

                new_T = calc_T()
                gain = new_T - current_T

                # 元に戻す
                if typ == 'v':
                    door_h[ei][ej] = -1
                else:
                    door_v[ei][ej] = -1
                if old_sw_val != -1:
                    switch[si][sj] = old_sw_val
                else:
                    switch[si][sj] = -1
                if not used_switch[k]:
                    switch_pos[k] = old_sw_pos
                    used_switch[k] = old_used

                if gain > best_gain:
                    best_gain = gain
                    best_door = (typ, ei, ej)
                    best_sw_pos = cand_sw

            if best_gain > 0 and best_door is not None:
                # 設置確定
                typ, ei, ej = best_door
                if typ == 'v':
                    door_h[ei][ej] = 2 * k + 1
                else:
                    door_v[ei][ej] = 2 * k + 1
                si, sj = best_sw_pos
                if not used_switch[k]:
                    switch[si][sj] = k
                    switch_pos[k] = (si, sj)
                    used_switch[k] = True
                else:
                    # 既存のスイッチをより遠くへ移動
                    old_si, old_sj = switch_pos[k]
                    switch[old_si][old_sj] = -1
                    switch[si][sj] = k
                    switch_pos[k] = (si, sj)
                doors_placed += 1
                current_T, current_path = calc_T_with_path()
                improved = True
            else:
                # このスイッチ種類では改善不可
                if not used_switch[k]:
                    # スイッチだけでも設置（入口から最遠）
                    best_sw = None
                    max_d = -1
                    for si in range(N):
                        for sj in range(N):
                            if grid[si][sj] == '.' and switch[si][sj] == -1:
                                d = bfs_reachable(0,0,0)[si][sj]
                                if d > max_d and d != -1:
                                    max_d = d
                                    best_sw = (si, sj)
                    if best_sw:
                        si, sj = best_sw
                        switch[si][sj] = k
                        switch_pos[k] = (si, sj)
                        used_switch[k] = True
                break

    # ----- 出力 -----
    doors = []
    for i in range(N-1):
        for j in range(N):
            if door_h[i][j] != -1:
                doors.append((0, i, j, door_h[i][j]))
    for i in range(N):
        for j in range(N-1):
            if door_v[i][j] != -1:
                doors.append((1, i, j, door_v[i][j]))
    print(len(doors))
    for d, i, j, g in doors:
        print(d, i, j, g)

    switches_out = []
    for i in range(N):
        for j in range(N):
            if switch[i][j] != -1:
                switches_out.append((i, j, switch[i][j]))
    print(len(switches_out))
    for i, j, s in switches_out:
        print(i, j, s)

if __name__ == "__main__":
    solve()

提出情報

ジャッジ結果