3

とのサイズNxMの行列が与えられます。マウスが に存在する場合は 、存在しない場合は になります。から開始し、到達する必要があります。下に行くか、右にしか行けません。そのような位置を通過すると、その位置のマウスは私たちを怖がらせます。01[i:j]10[0:0][n-1:m-1][i:j][x:y]|i-x|+|j-y|<=1

最小数の異なるマウスで怖がる経路を見つけます。明確な言葉、つまりマウスが私たちを怖がらせた場合、それは再び私たちを怖がらせることはありません。

この質問はインタビューで聞かれました。一般的なDP問題で使用されるアイデアで解決しようとしました。ここでは、上下に移動して最小パスを見つける必要がありますが、これらすべての問題で、最小値を取得[i-1:j]し[i:j-1]て現在のインデックスの最小値を見つけ、すべての行を下に処理できます左から右へ。

しかし、ここではマウスが 4 つのセルに影響を与えるため、このアイデアを使用することはできません。

誰かがこれを解決する方法を教えてもらえますか?

4

4 に答える 4

1

この問題に対処する最も簡単な (十分に効率的ではない) 方法は、次のエッジ コスト関数 (i と j はセル (i',j') を参照するグラフ ノード) を使用して、NxM 頂点のグラフの最短経路を解くことだと思います。および (i'',j'') メイン マトリックス):

c(i,j) = 1 if [(i',j') and (i'',j'') are sideByside] && [(i'',j'') is scaring] ,
         0 otherwise
于 2013-06-09T07:33:47.690 に答える