[BOJ]15488夜に碁盤が出ない確率

7749 ワード
テキストリンク
https://www.acmicpc.net/problem/15488
ナイトがK号を任意に移動する際、チェス盤を離れず、他の人がいる確率を求める問題だ.
一般的な方法で問題を解くとタイムアウトになります(実際、私はすでに問題の分類を見たことがあります...)DPを使用して各ラウンドの状態を保存し、リリースする必要があります.
n回移動すると、ある格子(i,j)にナイトが存在する確率pがある場合、n+1回の周囲8格子(ナイトが行ける)にナイトが存在する確率はいずれもp/8である.
この操作は、N^2のすべてのセルに対して行い、碁盤から離れることを無視すればよい.

プールコード

import sys

input = sys.stdin.readline

dy = [2, 1, -1, -2, -2, -1, 1, 2]
dx = [1, 2, 2, 1, -1, -2, -2, -1]

def main():

    N, x, y, K = map(int, input().split())
    B = [ [0 for _ in range(N)] for _ in range(N) ]
    B[y-1][x-1] = 1

    for _ in range(K):
        temp = [ [0 for _ in range(N)] for _ in range(N) ]
        for i in range(N):
            for j in range(N):
                for d in range(8):
                    ny, nx = i + dy[d], j + dx[d]
                    if 0 <= ny < N and 0 <= nx < N:
                        temp[ny][nx] += B[i][j] * 0.125
                        
        B = temp
    print(sum(map(sum, B)))


main()
シンプルなローダをCSSと
デイリーツーセント