大致题意:
问从图中的'.'到另一个'.',中间最多只能拐一个九十度的弯,最远的距离是多少
大致思路:
一开始用记忆化搜索感觉没有头绪。但是仔细思考后发现(以左侧为例)这个点左侧的点数是可以通过其左边的点递推得到的,于是直接用递推得到每个点各个方向上的点数。
推完之后遍历这个图,把每个点假设为拐点,得到所有点两个方向上和的最大值即为答案。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; char mapp[104][104]; int dp[104][104][10]; int n; //012 //7*3 //654 bool inmap(int x,int y){ if(x>=0&&x<n&&y>=0&&y<n){ if(mapp[x][y]=='.')return 1; } return 0; } int main(){ int i,j,k; while(cin>>n&&n){ for(i=0;i<n;i++){ cin>>mapp[i]; } memset(dp,0,sizeof(dp)); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(mapp[i][j]=='#')continue; if(inmap(i-1,j-1)){ dp[i][j][0]=dp[i-1][j-1][0]+1; } if(inmap(i-1,j)){ dp[i][j][1]=dp[i-1][j][1]+1; } if(inmap(i-1,j+1)){ dp[i][j][2]=dp[i-1][j+1][2]+1; } if(inmap(i,j-1)){ dp[i][j][7]=dp[i][j-1][7]+1; } } } //012 //7*3 //654 for(i=n-1;i>=0;i--){ for(j=n-1;j>=0;j--){ if(mapp[i][j]!='.')continue; if(inmap(i,j+1)){ dp[i][j][3]=dp[i][j+1][3]+1; } if(inmap(i+1,j+1)){ dp[i][j][4]=dp[i+1][j+1][4]+1; } if(inmap(i+1,j)){ dp[i][j][5]=dp[i+1][j][5]+1; } if(inmap(i+1,j-1)){ dp[i][j][6]=dp[i+1][j-1][6]+1; } } } int res=0; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(mapp[i][j]!='.')continue; for(k=0;k<=5;k++){ res=max(res,(dp[i][j][k]+dp[i][j][k+2]+1)); } res=max(res,(dp[i][j][0]+dp[i][j][6]+1)); res=max(res,(dp[i][j][1]+dp[i][j][7]+1)); } } printf("%d\n",res); } return 0; }
相关推荐
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc