mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ yukicoder 問題 No.340 雪の足跡 - yukicoder 解法 ある頂点から進むことのできる方向に制限ができるので, それを基に幅優先探索するのが基本です。ただ, 進むことの出来る方向を愚直に決定すると から の間で, 進む方向をメモするのに最悪 O(W) (O(H)) かかって, 入力に現れる は O(NM) だけあるので, 時間制限に間に合いません。想定解では, これを解決するためにいもす法を使っていますが, 少し別の方法でやりました。migi[y][x] = (頂点 (y, x) から右側にどれだけいけるか) というのを考えます。入力がなにもない状態では, migi[y][x] = x です… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F01%2F30%2F110508" title="yukicoder No.340 雪の足跡 - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-01-30 11:05:08 rich https://mayokoex.hatenablog.com/entry/2016/01/30/110508 1.0 100%