[python]伯俊20152 Game Addression

5089 ワード

質問する
江山は深刻なゲーム中毒者で、天気にかかわらず、毎日ネットカフェに行きます.
最近の豪雨で一部の地域が水没し、水没した地域に移動できなかった.しかし、江山はイベントに出席するため、毎日ネットカフェに行く.
江山は上、下、左、右方向にネットカフェに移動するだけで、1回の移動距離は1です.また、江山はゲームをしに行くので、家からネットカフェまで最短ルートを歩かなければなりません.
江山家の座標(H,H)とネットカフェの座標(N,N),座標平面上(x,y)上y>xの場所が水没した場合,水没した地域を避けてネットカフェに到達する経路の個数を求める.
しかし、ネットカフェの座標が家の座標であれば、経路は1種類です.
入力
1行目には,家とネットカフェ座標(H,H),(N,N)を表す2つの整数H,N(0≦H,N≦30)が順次与えられる.
しゅつりょく
家からネットカフェまでのパス数を出力します.
入力例1
8 4
サンプル出力1
14
入力例2
0 3
サンプル出力2
5
コード#コード#
# 20152 Game Addiction

H, W = map(int, input().split())

start = 0
end = abs(H - W) + 1

numbers = [[0] * end for _ in range(end)]
for i in range(end):
    numbers[0][i] = 1

for i in range(1, end):
    for j in range(i, end):
        numbers[i][j] = numbers[i - 1][j] + numbers[i][j - 1]

ans = numbers[-1][-1]
print(ans)

(コードにstart=0は不要…)
解説
座標値を求める場合、HとWの値が何であるかは重要ではありません.
重要なのはH,W間の差がどれほど大きいかである.
H=0,W=5のとき和
H=5,W=10の場合の結果は同じですから.
H=10,W=5の場合の結果も同様である.
場合によっては、左上から右下にかけて対角線を引くと、上の部分が水没します.
状況数を求めるときは、底部を浸水と見なしてもいいです.便宜上、下に水が浸かっていると思います.
0、0から3、3の場合、すべてのセルに数値を書き込むと、次のように移動します.
1 1 1 1
0 1 2 3
0 0 2 5
0 0 0 5
8、8~4、4の数字は0、0~4、4の数字と同じです.
0、0から4、4までの場合、同様に全てのケース数を記録すると、
1 1 1 1 1
0 1 2 3 4
0 0 2 5 9
0 0 0 5 14
同じ結果が得られます.
目の先の読者はとっくに気づいているかもしれない.
私が解く方法は以下の通りです.
  • H,Wの差を求める.
  • N = abs(H - W) + 1
  • N*N配列を作成し、0に初期化します.
  • 最初の行は1を入れます.
  • [1,1]から、上と左の値を加算します.
  • すべての場合の数を簡単に求めることができることは明らかである.