207394848R @ 2022-06-06 11:10:58
#include <iostream>
#include <string.h>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<climits>
#include<map>
#include<queue>
using namespace std;
const int maxn = 100 + 10;
int towards[4][2] = {
{1,0},{-1,0},{0,1},{0,-1}
};
struct Node{
int x, y;
int height;
}orders[maxn * maxn];
bool cmp(Node a, Node b)
{
return a.height < b.height;
}
int n, m, nums[maxn][maxn], numsCopy[maxn][maxn], maxnum, steps[maxn][maxn], maxStep = 0;
int main()
{
fill(steps[0], steps[0] + maxn * maxn, 1);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> nums[i][j];
numsCopy[i][j] = nums[i][j];
orders[m * i + j].height = nums[i][j];
orders[m * i + j].x = i;
orders[m * i + j].y = j;
}
}
/*for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
printf("%d (%d,%d,%d)\n", nums[i][j], orders[m * i + j].x, orders[m * i + j].y, orders[m * i + j].height);
}
}*/
sort(orders, orders + n * m, cmp);
/*for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
printf("(%d,%d,%d)\n", orders[m * i + j].x, orders[m * i + j].y, orders[m * i + j].height);
}
}*/
maxnum = orders[0].height;
for (int i = 0; i < n*m; i++)
{
Node newNode;
for (int j = 0; j < 4; j++)
{
//cout << towards[i][0] << " " << towards[i][1];
newNode.x = orders[i].x + towards[j][0];
newNode.y = orders[i].y + towards[j][1];
newNode.height = numsCopy[newNode.x][newNode.y] + nums[orders[i].x][orders[i].y];
if (numsCopy[newNode.x][newNode.y] < orders[i].height)
{
continue;
}
if (newNode.x >= 0 && newNode.x < m &&
newNode.y >= 0 && newNode.y < n)
{
if (newNode.height>nums[newNode.x][newNode.y])
{
nums[newNode.x][newNode.y] = newNode.height;
steps[newNode.x][newNode.y] = steps[orders[i].x][orders[i].y] + 1;
if (nums[newNode.x][newNode.y] >maxnum)
{
maxnum = nums[newNode.x][newNode.y];
}
}
else
{
continue;
}
}
else
{
continue;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (nums[i][j]==maxnum)
{
cout << steps[i][j];
}
}
}
return 0;
}```cpp
我的想法是用一个数组按高度从小到大排序order,再按那个顺序,把点的高度向周围更高的扩散nums。最后得到最高的高度maxnum。因为没看清输出,步数steps后加的应该没问题啊
by IamYoung2021 @ 2022-07-02 11:38:24
建议使用记忆化搜索
还有,你是TLE了,还是WA了?