けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

枝刈りBFS

AtCoder ABC 246 E - Bishop 2 (水色, 500 点)

迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう!! 頂点の持ち方を工夫して 0-1 BFS で解く! 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…