java - 王様の迷路

Question

プログラミングコンテストに向けて練習していて、過去に答えることができなかったいくつかの難しい問題に取り組んでいます。それらの 1 つは王の迷路でした。-50<x<50基本的に、 「トークン」を表す数値の NxN 配列が与えられます。位置 1,1 から開始し (配列インデックスでは 0,0 であると仮定します)、N,N で終了する必要があります。訪問したセルでトークンを取得する必要があり、トークンのないセル (0 で表される) を踏むことはできません。0 に囲まれると負けです。迷路に解決策がない場合は、「解決策なし」と出力します。それ以外の場合は、拾ったトークンを合計して得られる最大の数を出力します。

この問題を解決する方法がわかりません。それを解くための迷路アルゴリズムを書けると思ったのですが、それには時間がかかります。プログラミング コンテストでは、複数の問題を解くのに 2 時間しか与えられません。見落としているパターンがあると思います。これにどのようにアプローチすればよいか知っている人はいますか？

また、この問題は高校生向けであることを言及しておくと役立つかもしれません。

Answer 1

この種の問題は通常、動的計画法またはメモ化を使用して解決されます。

基本的に、再帰的なソリューションを定式化し、以前に計算された結果を記憶して再利用しながら、ボトムアップで解決します。

Answer 2

単純なアプローチ (つまり、コーディングが最も簡単) は、考えられるすべてのパスを試すことです。最初の各ステップを試してください。最初のステップごとに、2 番目のステップをそれぞれ試してください。最初のステップと 2 番目のステップの組み合わせごとに、3 番目のステップをそれぞれ試します。等々。ただし、迷路の大きさによっては、実行に時間がかかりすぎる場合があります (またはそうでない場合もあります)。

次のステップは、これをより速く行う方法を考えることです。通常、最初のステップは、フィニッシュにつながらないことがわかっている動き、またはすでに持っているポイントよりも高いポイントでフィニッシュにつながらないことがわかっている動きを排除することです。これはコンテストの練習なので、この作業は自分で行うようにしてください。

Answer 3

「グラフ」アルゴリズムを考える:アルゴリズム設計マニュアル