Booby Traps (UVa Live Archive Europe - Southwestern - 2006/2007 Lisbon (Portugal))

トラップが仕掛けられた幅w、高さhの迷宮を探索したい。トラップは26種類存在し、あるトラップを作動させてしまうと、それ以下の優先度のトラップは全て作動し、トラップのあった場所は通れなくなってしまう。
最短何歩でゴールまでたどり着けるか。
h*w<=40000

どのトラップまで作動したかで頂点数を27倍に増やしてbfs。