質問する

時間制限:2秒

メモリ制限:256 MB

Problem Analysis

最適なパスを選択できるルールはなく、可能な限りすべての状況を調査するしかありません.これまでの経路を一緒に保存して、巡回すればいいです.
この場合、k距離の同じセルであっても通過経路によって異なるため、BFSを行うとQueueに指数的に追加される.これに対し、DFSは距離によって積み重ねられるため、メモリへの負担は相対的に小さくなります.

Algorithm

DFSで問題を解決します.
隣接するセルの場合、

行、列の範囲

パス冗長性(ビットマスクを使用して各アルファベットにアクセスするかどうかを記録する)

満たされると、次のカウントが再帰的に呼び出されます.
return値から最大値を選択

Data Structure

ボード[r][c]、ストレージボード

seqBits、ビットシールド検査

count,DFS深さ検査

結果

Other

1 2 3
4 5 6
7 8 9

通常、BFSが1から始まる場合、5を1−2−5の順でQueueに入れ、1−4−5の順でアクセスする場合、アクセスした5はQueueに追加されない.ただし,この問題では距離は重要ではなく,経路の違いを考慮する必要があるため,5を追加する必要がある.
この追跡問題において,DFSはBFSよりも容易で直感的である.