Lineng @ 2021-12-09 13:25:58
我的思路是d[i][j]表示的是在这个高度下,能滑到的最低点,不是表示距离,距离在最后再计算,觉得思路也没有问题,但是只有60pts,还麻烦大佬看看
d[i][j]我初始化为最大值,因为要找最小的可到达点
pair我存了4个方向
越界判断在insert函数
#include <bits/stdc++.h>
using namespace std;
#define maxn 210
int a[maxn][maxn], d[maxn][maxn];
int r, c;
pair<int, int> p[3];
void initial()
{
memset(d, 0x3f3f3f3f, sizeof(d));
p[0].first = 0, p[0].second = -1;
p[1].first = 0, p[1].second = 1;
p[2].first = -1, p[2].second = 0;
p[3].first = 1, p[3].second = 0;
}
bool insert(int i, int j)
{
return i >= 0 && i < r && j >= 0 && j < c;
}
int dp(int r, int c)
{
//如果搜索过
if (d[r][c] != 0x3f3f3f3f)
return d[r][c];
d[r][c] = a[r][c];
for (int k = 0; k < 4; k++)
{
int i = p[k].first;
int j = p[k].second;
if (insert(r + i, c + j))
{
if (a[r][c] > a[r + i][c + j])
d[r][c] = min(d[r][c], dp(r + i, c + j));
else
d[r][c] = min(d[r][c], a[r][c]);
}
}
return d[r][c];
}
int main()
{
cin >> r >> c;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> a[i][j];
initial();
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
dp(i, j);
int ans = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
ans = max(ans, a[i][j] - d[i][j]);
cout << ans + 1;
return 0;
}
by PIIN_TOF @ 2022-01-17 11:11:09
同这几个WA了,求助