質問リンク

15684-はしご操作

問題の説明

問題を解く

試してみる。

dfsを用いてバックグラウンド追跡を試みた.Tekeが出てきたのはすべて正しいですがタイムアウトが発生しました^ㅠ

import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline

N, M, H = map(int, input().split())
board = [[0] * N for _ in range(H)]
minval = 4
ladders = set()

for i in range(M):
    x, y = map(int, input().split())
    ladders.add((x-1,y-1))

def play(board):
    visited = [[0]*N for _ in range(H)]
    for i in range(N):
        cur_x, cur_y = 0, i
        visited[cur_x][cur_y] = 1
        while cur_x < H:
            if cur_y+1 < N and visited[cur_x][cur_y+1] != 1 and (cur_x, cur_y) in ladders:
                cur_y += 1
            elif cur_y-1 >= 0 and visited[cur_x][cur_y-1] != 1 and (cur_x, cur_y-1) in ladders:
                cur_y -= 1
            else:
                cur_x += 1
            if cur_x < H:
                visited[cur_x][cur_y] = 1
        if i != cur_y:
            return False
    return True

def dfs(count, board):
    global minval
    if count > 3:
        return
    
    if play(board):
        minval = min(minval, count)
        return

    for i in range(H):
        for j in range(N-1):
            if (i, j) not in ladders:
                if j-1 >= 0 and j+1 < N and (i, j-1) not in ladders and (i,j+1) not in ladders:
                    #사다리 설치
                    ladders.add((i,j))
                    dfs(count+1, board)
                    ladders.remove((i, j))
                elif j+1 < N and (i, j+1) not in ladders:
                    #사다리 설치
                    ladders.add((i,j))
                    dfs(count+1, board)
                    ladders.remove((i, j))
                elif j-1 >= 0 and (i, j+1) not in ladders:
                    #사다리 설치
                    ladders.add((i,j))
                    dfs(count+1, board)
                    ladders.remove((i, j))
dfs(0, board)

if minval == 4:
    print(-1)
else:
    print(minval)

試してみる。

いったいどこを減らせばいいのか、長い間考えていた後、dfsが回転する部分では、毎回(0,0)から探索するのではなく、以前に検査した部分から探索を開始する.pypy 3で危うく通過^ㅠ

import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline

N, M, H = map(int, input().split())
board = [[0] * N for _ in range(H)]
minval = 4
ladders = set()

for i in range(M):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

def play(board):
    for start in range(N):
        cur_y = start
        for cur_x in range(H):
            if board[cur_x][cur_y] == 1:
                cur_y += 1
            elif cur_y > 0 and board[cur_x][cur_y-1] == 1:
                cur_y -= 1
        if start != cur_y:
            return False
    return True

def dfs(count, x, y):
    global minval
    if play(board):
        minval = min(minval, count)
        return
    if count == 3 or minval <= count:
        return
    for i in range(x, H):
        k = y if i == x else 0
        for j in range(k, N-1):
            if board[i][j] == 0 and board[i][j+1] == 0:
                board[i][j] = 1
                dfs(count+1, i, j+2)
                board[i][j] = 0
            
dfs(0, 0,0)

if minval == 4:
    print(-1)
else:
    print(minval)