首页 > 代码库 > poj1088 滑雪(dfs、dp优化)
poj1088 滑雪(dfs、dp优化)
#include <iostream> #include <map> #include <string> #include <cstdio> #include <sstream> #include <cstring> #include <vector> #include <cmath> #define N 110 int a,b,step=0; int anw=0; int moun[N][N]; int dp[N][N]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; using namespace std; int dfs(int curx,int cury){ int nextx,nexty,steps=1; if(dp[curx][cury]>1) return dp[curx][cury]; for(int i=0;i<4;i++) { nextx=curx+dir[i][0]; nexty=cury+dir[i][1]; if(nextx>=0&&nextx<a&&nexty>=0&&nexty<b&&moun[nextx][nexty]<moun[curx][cury]) { dp[curx][cury] = dfs(nextx,nexty)+1; if(dp[curx][cury]>steps){ steps=dp[curx][cury]; } } } dp[curx][cury]=steps; return steps; } int main(){ scanf("%d %d",&a,&b); anw=0; memset(dp,0,sizeof(dp)); for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ scanf("%d",&moun[i][j]); dp[i][j]=0; } } for(int i=0;i<a;i++){ for(int j=0;j<b;j++) { step=dfs(i,j); if(step>anw) anw=step; } } printf("%d\n",anw); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。