No.3375 Binary Grid
解説を見てもよく分からず、テストケースを見てデバッグしてAC。苦労した。
再帰構造は明らかなので、それを使って計算するしかない。
しかし、帰り道でどう再帰するかが難しい。
(x,y) から(R,C)へ移動するとき（x>=R,y>=Cとする）、R行の中で、yからCの間に通れないマスがあるか？ を考える。
なければ、max(x-R,y-C)が答え。
R行の中で、最も大きい通れないマスの列番号kとしたとき、（R,k）から下に行った先で初めて進めるマス、そこを必ず通らなくてはいけない。
それを使えば再帰できる。
0 件のコメント:
コメントを投稿