-1

与えられた 2D 配列で、減少する数の最長のシーケンスを見つけます。制約は次のとおりです。 1. 要素を斜めに比較することはできません。

例:

56 14 51 58 88
26 94 24 39 41
24 16 8 51 51
76 72 77 43 10
38 50 59 84 81
5 23 37 71 77
96 10 93 53 82
94 15 96 69 9
74 0 62 38 96
37 54 55 82 38

ans は次のとおりです: 7

そして以下のマトリックスについて

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

25 -> 24 -> 23 -> 22 -> …というように 1 に到達するまで続けます。

誰かがアルゴリズムを手伝ってくれませんか。

これは私の最初のコードでした：

int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};

int findSequence(int x, int y)
{
    for(int i = 0; i < 4; ++i)
    {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if(isValid(new_x, new_y) && data[x][y] > data[new_x][new_y])
        {
            std::cout << "" << data[x][y] << " -> " << data[new_x][new_y] << " ";
            int tmp =  1 + findSequence(new_x, new_y, isVisited);
            //std::cout << " "<< tmp << " ";
            return tmp;
        }
    }
}

ありがとう

4

3 に答える 3

1

再帰を使用できます。インデックスから始まる最大シーケンスを取得したいとします(i,j)。次に、A が 2D 配列の(i1,j1)場合、4 番目の方向のいずれかに移動できます。A[i][j] > A[i1][j1]

const int N=50;
int A[N][N];
int res=0; // maximum result

int calc(int i, int j) {
    int r=1;   // only this element forms a single element sequence
    if(A[i][j]>A[i][j+1]) r=max(r, 1+ calc(i, j+1));
    if(A[i][j]>A[i][j-1]) r=max(r, 1+ calc(i, j-1));
    if(A[i][j]>A[i+1][j]) r=max(r, 1+ calc(i+1, j));
    if(A[i][j]>A[i-1][j]) r=max(r, 1+ calc(i-1, j));
    res=max(res,r);
    return r;
}

複雑さ: 結果が 2D 配列にメモ化されている場合は O(mn) (m は行数、n は列数)。

于 2015-08-06T09:52:13.840 に答える