質問リンク

移動パイプ1

問題の説明

N*Nサイズの仕切り(1,1)、(1,2)にパイプが置かれています.パイプを(N,N)格に押したいのですが、→、演繹、↓の3方向に押すしかありません.パイプは押しながら回すことができます.回転は45度しか回転できません.回転方向は右、下または右下の対角方向でなければなりません.
次の図は、パイプが配置方向に押すことができる数を示しています.



壁を避けてパイプをN*Nに押すことができれば、数を求めます.

問題を解く

Googleゲームでは、パイプ移動の問題には2つの異なる条件があります.パイプ移動1はN(3≦N≦16)で1秒、パイプ移動2はN(3≦N≦32)で0.5秒、、、
「パイプ転移1」はdfsで、「パイプ転移2」はdpで解くために発生した問題のようで、pythonを使ってdfsで1を解くとタイムアウトになるので、どちらもdpで^ㅠ

1-dfsを試します

dfsを迂回し,現在の方向に移動できるすべての場合,再帰を迂回した.89%タイムアウト^ㅠ

import sys

input = sys.stdin.readline

N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
pipe = [0,1]
pipe_dir = 0 #0:가로, 1:세로, 2:대각선
answer = 0

def in_range(x, y):
    if x in range (N) and y in range(N):
        return True
    return False

def dfs(x, y, pipe_dir):
    global answer
    if x == N-1 and y == N-1:
        answer += 1
        return
    #가로인 경우
    if pipe_dir == 0 or pipe_dir == 2:
        if in_range(x, y+1) and board[x][y+1] == 0:
            dfs(x, y+1, 0)
    if pipe_dir == 1 or pipe_dir == 2:
        if in_range(x+1, y) and board[x+1][y] == 0:
            dfs(x+1, y, 1)
    if in_range(x+1, y+1) and board[x][y+1] == board[x+1][y] == board[x+1][y+1] == 0:
        dfs(x+1, y+1, 2)

dfs(pipe[0], pipe[1], pipe_dir)
print(answer)

2-dpを試みる

dpアレイを方向を含む3次元アレイに作成して解く.

ステータスの定義

d[x][y][dir]d[x][y][dir]d[x][y][dir]:dir方向で(x,y)に達できる数
横:d[x][y][0]=d[x][0]+d[x][y-1][x][x][y]=d[x][y-1][x-1][y-1][y-1][2]d[x][y][0]=d[x][x][x][y][0]]]][y]][0]][0]+d[0]+d[x][x]+d[y][x]+d[y]
縦画面:d[x][y][1]=d[x]-[y]+d[x-1][y]d[x][x][y]][x]-1]d[x-1][y][y][y][2]d[x][y][1]=d[x21][y][y][y][y]][y]][x[1]]]][y][y]][y]][y]][y]][x]][[y]]][[x]]]]]]]][[1]+d[y][y][y][x]+d[x][[x]
[x][x][y][y][y][y][2]=d[xは1][0][0]+d[xͧ1][y]871;;;1][1][xxxxxxxx][2][x][x][x][x-1][x-1][x-1][x-1][x-1][x-1][[x-1][x-1][x-1][x-1][x-1][x-1][x-1][x-1][x-1][xx-1]][[x-1][[x-1]][[xx-1][[[x-1]]][[[x-1]]]][[[[x-1]]]]]][[[[[[[[xxx-1]]]]]]]]][[[[[[[[[[[[[[[xxxxxxxxⓐ1][ⓐ1]+1]+d[ⓐ1][ⓐ1][2]
初期状態にあるdp[0][1][0]では,数を1に初期化し,移動可能な範囲(0,2)から砲口を回して各方向を計算する.パイプは2つの格子を占めていますが、(0,1)から(N-1,N-1)までで良いので、1つだけ考えてもいいです.

import sys

input = sys.stdin.readline

N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))
pipe = [0,1]
pipe_dir = 0 #0:가로, 1:세로, 2:대각선
dp = [[[0]*3 for _ in range(N)] for _ in range(N)]
dp[0][0][0] = 1
dp[0][1][0] = 1

for x in range(N):
    for y in range(2, N):
        #대각선으로 이동
        if board[x][y-1] == board[x-1][y] == board[x][y] == 0:
            dp[x][y][2] = dp[x-1][y-1][0] + dp[x-1][y-1][1] + dp[x-1][y-1][2]
        
        if board[x][y] == 0:
            #가로로 이동
            dp[x][y][0] = dp[x][y-1][0] + dp[x][y-1][2]
            #세로로 이동
            dp[x][y][1] = dp[x-1][y][1] + dp[x-1][y][2]

print(dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2])