xijue_08 @ 2020-10-28 09:51:57
按照题解的思路,谷底对应的值是1。 为什么谷底对应的值不是0,也就是滑不了呢?
#include<iostream>
#include<vector>
using namespace std;
/*
例如测试用例
4 4
10 9 8 7
10 5 8 8
10 9 9 9
10 9 9 9
输出
0 0 0 0 0 0
0 4 3 2 1 0
0 1 0 1 2 0
0 2 1 2 3 0
0 2 1 1 1 0
0 0 0 0 0 0
*/
static int longest = 0;
static int R = 0;
static int C = 0;
static int m[102][102];
static int dp[102][102];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void ski(int x, int y) {
if(dp[x][y]) return;
int xx, yy;
for(int i = 0; i < 4; i++) {
xx = x + dx[i];
yy = y + dy[i];
if(xx >= 0 && yy >= 0 && xx <= R+1 && yy <=C+1 && m[x][y] > m[xx][yy]) {
ski(xx, yy);
dp[x][y] = max(dp[x][y], dp[xx][yy]+1);
}
}
}
int main () {
cin>>R>>C;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
cin>>m[i][j];
}
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
ski(i, j);
longest = max(longest, dp[i][j]);
}
}
/*cout<<endl;
for (int i = 0; i <= R+1; i++) {
for (int j = 0; j <= C+1; j++) {
cout<<dp[i][j]<<' ';
}
cout<<endl;
}*/
cout<<longest;
return 0;
}
by watermonster @ 2020-10-28 11:04:03
by xijue_08 @ 2020-10-28 12:39:59
@LSG_watermonster 是的,我这里的dp就是别人题解中的s,表示此点可以滑行的最大距离
by watermonster @ 2020-10-28 13:04:43
@xijue_08 谷底自己也算长度啊所以是1
by xijue_08 @ 2020-10-28 13:49:03
@LSG_watermonster 哦哦,是这样的么,我可能理解错了,我是觉得例如中间的谷底(就是代码中例子的5位置)四周都没有办法滑,所以是0来着。。。但是这么理解不对。 把基础值设成1就过了