小豆子范德萨 @ 2020-03-30 11:37:52
#include <bits/stdc++.h>
using namespace std;
int a[110][110];
int dp[110][110]; //dp[i][j]代表从i,j坐标上下左右的滑坡距离
int dir[4][2] = {
{-1,0},
{1,0},
{0,-1},
{0,1}
};
int r,c;
bool inside(int i,int j) { //判断边界
if(i < 0 || i >= r || j < 0 || j >= c) return false;
return true;
}
int dfs(int i,int j) { //v当前滑雪距离
if(dp[i][j]) return dp[i][j];
dp[i][j] = 1;
for(int k = 0;k < 4;k++) {
int newi = i + dir[k][0];
int newj = j + dir[k][1];
if(inside(newi,newj) && a[newi][newj] < a[i][j]) {
cout<<"newi:->"<<newi<<"newy->:"<<newj<<"\n";
int t = dfs(newi,newj);
return dp[i][j] = max(dp[i][j],t+1);
}
}
}
int main() {
cin>>r>>c;
for(int i = 0;i < r;i++) {
for(int j = 0;j < c;j++) scanf("%d",&a[i][j]);
}
int ans = 0;
for(int i = 0;i < r;i++) { //从该点出发到达的最长距离
for(int j = 0;j < c;j++) {
ans = max(ans,dfs(i,j));
}
}
cout<<ans;
return 0;
}
照着题解敲得找不到bug,输出是15,不是25,求大神帮忙看下
by Ryo_Yamada @ 2020-03-30 11:51:37
@小豆子范德萨
return dp[i][j] = max(dp[i][j],t+1);
这里直接return的话下面如果有更大的答案就找不到了,应该先4种情况都取一遍max,最后再return dp[i][j];
by 小豆子范德萨 @ 2020-03-30 11:56:54
@breeze末影 谢谢,但是先dfs不是要用返回值接么?
by Ryo_Yamada @ 2020-03-30 11:58:22
@小豆子范德萨 因为你向4个方向dfs的结果不一定相同,所以需要dfs4个方向,才能保证取到最大值。
by Ryo_Yamada @ 2020-03-30 11:59:42
@小豆子范德萨 可以这么写(没测过,但应该是对的
int dfs(int i,int j) { //v当前滑雪距离
if(dp[i][j]) return dp[i][j];
dp[i][j] = 1;
for(int k = 0;k < 4;k++) {
int newi = i + dir[k][0];
int newj = j + dir[k][1];
if(inside(newi,newj) && a[newi][newj] < a[i][j]) {
//cout<<"newi:->"<<newi<<"newy->:"<<newj<<"\n";
int t = dfs(newi,newj);
dp[i][j] = max(dp[i][j],t+1);
}
}
return dp[i][j];
}
by 小豆子范德萨 @ 2020-03-30 12:00:04
@breeze末影 对的,对的。谢谢大神