ちょっと、各要素が高さの値を保持する 2D マトリックスがあります。マトリックスの例は次のようになります。
1 2 3 6 5 4 7 8 9
次の基準を満たす最長パスを見つけようとしています。
– element[i] > element[i + 1] (選択したパスの次の要素は、現在の要素よりも下にあります) （下）
– element[i] == element[i + 1] (選択したパスの次の要素は、現在の要素と同じです) （真っ直ぐ）
– 上、下、左、右の 4 方向にしか移動できないことに注意してください。
さらに、パスには、値が減少する可能な最大量のセグメントと、値が同じままである可能な最小量のセグメントが含まれている必要があります。
上記の例のマトリックスの解決策は次のとおりです。
9-8-7-6-5-4-3-2-1 (8 segments down, 0 segments straight)
減少するパスを見つけること自体は非常に簡単で、解決された例が複数ありますが、値が同じままであるセグメントで機能するアルゴリズムを考案するのに苦労しています.
例として、次のマトリックスを取り上げます。
0 1 2 2 2 2 3 4 5
このマトリックスの正しいパスは次のようになります。
5-4-3-2-2-1-0 (5 segments down, 1 segment straight)
以下は同じマトリックスですが、わかりやすくするために未訪問のセルは削除されています
0 1 2 2 3 4 5
私が試したこと：
マトリックスのすべての要素から最長のパスを見つけようとしましたが、上記の基準を満たすものを選択しました (最大セグメントが下、最小セグメントがまっすぐ)。
要素から最長パスを見つける
BFS を使用して、上記の条件に基づいて次のセルを選択しようとしましたが、メモリ テーブルを使用しても、より複雑な行列を正しく解くことができず、より多くの直線セグメントが含まれていると、実装で誤った結果が生成されます。 .
コメント