1

こんにちは私はスタックオーバーフローに不慣れです。Javaプログラムで以下の問題を解決するための助けが必要です

2D配列を使用しているので、任意のノードからトラバースできる最大長を見つける必要があります。現在の要素よりも値が小さい場合は、1つの要素から接続された要素（左/右/上/下）に移動できます。以下の2D整数配列で上記の条件で可能な最大パスを見つける必要があります5*5配列

  7  2  3  4  5 
  36 37 38 34 6 
  33 44 46 40 7 
  24 43 42 41 8 
  35 32 47 30 9

上記の配列の最長パスは46-44-43-42-41-30-9-8-7-6-5-4-3-2合計14です。

このJavaコードの記述を手伝ってください。よろしくお願いします。

4

1 に答える 1

1

データをグラフとして表す、ここでG=(V,E)およびV={ all squares}、E = { (u,v) | u is adjacent to v and u.value < v.value)

上記のグラフは有向非巡回グラフであることに注意してください((u,v) が E にある場合、 からvへのパスはありません。これは、 のようなuパスが必要になるためです。ただし、推移的であるため、 を意味します。にあるので矛盾しており、そのようなパスは存在できません)。v->v1->v2->...->uv.value > v1.value > v2.value > .... > u.valueoperator>v.value > u.valuev.value < u.value(u,v)E

この削減の後、より単純な問題である DAG の最長パスを簡単に解決できます。

于 2013-02-03T14:16:02.490 に答える