UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212687#3828. Bzhouzhichen123456200ms1240kbC++2.1kb2024-10-20 09:39:452024-10-20 14:36:15

answer

#include <iostream>

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

// 深度优先搜索函数
void dfs(int x, int y, int* path, int& pathLen, int** matrix, int n, int m, int* longestPath, int& longestPathLen) {
    int curVal = matrix[x][y];
    path[pathLen++] = curVal;

    if (pathLen > longestPathLen) {
        longestPathLen = pathLen;
        for (int i = 0; i < pathLen; ++i) {
            longestPath[i] = path[i];
        }
    } else if (pathLen == longestPathLen && std::lexicographical_compare(path, path + pathLen, longestPath, longestPath + longestPathLen)) {
        longestPathLen = pathLen;
        for (int i = 0; i < pathLen; ++i) {
            longestPath[i] = path[i];
        }
    }

    for (int i = 0; i < 4; ++i) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] > curVal) {
            dfs(newX, newY, path, pathLen, matrix, n, m, longestPath, longestPathLen);
        }
    }

    pathLen--;
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        int n, m;
        std::cin >> n >> m;
        int** matrix = new int*[n];
        for (int i = 0; i < n; ++i) {
            matrix[i] = new int[m];
            for (int j = 0; j < m; ++j) {
                std::cin >> matrix[i][j];
            }
        }
        int* longestPath = new int[n * m];
        int longestPathLen = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int* path = new int[n * m];
                int pathLen = 0;
                dfs(i, j, path, pathLen, matrix, n, m, longestPath, longestPathLen);
                delete[] path;
            }
        }
        std::cout << longestPathLen << std::endl;
        for (int i = 0; i < longestPathLen; ++i) {
            std::cout << longestPath[i] << " ";
        }
        std::cout << std::endl;
        for (int i = 0; i < n; ++i) {
            delete[] matrix[i];
        }
        delete[] matrix;
        delete[] longestPath;
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1236kb

input:

10
3 3
0 1 2
3 4 5
6 7 8
3 3
0 1 2
3 4 5
6 8 7
3 3
0 1 2
3 4 5
7 6 8
3 3
0 1 2
3 4 5
7 8 6
3 3
0 1 2...

output:

5
0 1 2 5 8 
6
0 1 2 5 7 8 
5
0 1 2 5 8 
6
0 1 2 5 6 8 
5
0 1 2 5 7 
7
0 1 2 5 6 7 8 
5
0 1 2 6 8 
6...

result:

ok 64 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 1240kb

input:

10
1 10
1 5 0 8 2 9 6 3 4 7
1 10
2 5 8 0 9 7 3 1 6 4
3 3
0 1 2
5 4 3
6 7 8
1 10
3 4 7 2 5 6 9 0 1 8
...

output:

3
3 4 7 
4
1 3 7 9 
9
0 1 2 3 4 5 6 7 8 
4
2 5 6 9 
3
1 7 9 
4
4 5 6 7 
3
0 4 7 
10
0 1 2 3 4 5 6 7 ...

result:

ok 63 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #3:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

10
2 100000
143604 106821 145034 44402 118718 156663 77133 28800 81890 12336 191537 118894 103331 75...

output:

13
11306 16007 49522 70570 76999 90088 97453 105217 116458 118241 145649 165150 168193 
9
9688 35806...

result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

10
1 200000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #7:

score: 0
Time Limit Exceeded

input:

10
145 1379
140324 86968 96426 123781 39754 103720 60835 118904 114639 53717 27146 110309 39232 5608...

output:

14
8850 11113 25989 34151 36456 84869 93686 115053 144522 160408 175609 177211 186680 198340 
14
701...

result: