5

以下は問題文です。

サイズ m*nの行列があり、1 から m*n までのすべての数値がその中の場所を占めます。今、要素は特別な場合と呼ばれます(再帰的な定義)

-it is the top left corner element(at position (0,0)) 
-an element at (x,y) is special if its neighbour is an element (m,n) such that (m,n) is    
 special and the element at (x,y) is greater than the element at(m,n) and all of the (m,n)'s neighbours.

セルの隣接セルは、セルとエッジを共有するセルです。したがって、内部セルには 4 つの隣接セルがあり、エッジ セルには 3 つの隣接セルがあり、コーナー セルには 2 つの隣接セルがあります。

この問題は、マトリックス内の数個の (おそらく 0 個の) セルのみが埋められていることを示しています。残りは、1 から m*n までのすべての数値が使用され、特殊要素の数が最大になるように埋められます。また、複数の回答が可能な場合は、辞書編集的に最小の行列が回答と見なされます。

行列は、その行優先ビューの文字列が他のものよりも辞書編集的に小さい場合、他のものよりも辞書編集的に小さくなります。

Test case 1: //2 X 3 matrix
2 ? ? 
? ? 3 

Solution 1:
2 1 4 
5 6 3 

Test case 2: //6 X 6 matrix
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 

Solution 2:
 1  2  3 13 14 15 
 4  6  8 10 11 16 
 5  7  9 12 19 17 
28 26 24 22 20 18 
29 27 25 23 21 36 
30 31 32 33 34 35

私の論理: マトリックス内の特別な要素は常に連続しています。したがって、隣接する特殊な要素を結合することによって形成される最長のパスを見つける必要があります。また、特別な要素 (m,n) の隣接セル (x,y) に要素を配置する前に、まず特別な要素 (m,n) のすべての隣接セル ((x,y) を除く) を埋めて、次に、それらすべてよりも大きい値を選択して (x,y) を埋めます。

先に進む方法と、辞書編集的に最小の条件を含める方法がわかりません。助けてください。

前もって感謝します。

4

1 に答える 1