ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212687 | #3828. B | zhouzhichen123456 | 20 | 0ms | 1240kb | C++ | 2.1kb | 2024-10-20 09:39:45 | 2024-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...