首页 > 代码库 > HDU 5024 Wang Xifeng's Little Plot(2014广州网络赛1003)
HDU 5024 Wang Xifeng's Little Plot(2014广州网络赛1003)
写了1h的DFS,简直被自己的代码吓哭了。。不过起码还是思路清晰,QUQ~
说一下题意吧: 题意是求一条最长路,最多能经过一次转弯,并且其角度只能为90度。
拿第一个样例来说:(0,1)->(1,2)->【转弯】(2,1) ,所以答案是3.
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5024
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cctype> #include<algorithm> #include<string> #include<map> #define N 111 #define LL long long using namespace std; int n,ans; char g[N][N]; //八个dfs因为要相互调用,故用类包装。 class dfs { public: //x,y,s分别表示坐标和路长,v是记录发生过几次转向。 void dfsl(int x,int y,int s,int v) //向左。 { ans=max(ans,s); if(y-1>=0 && g[x][y-1]=='.') //还能向左 dfsl(x,y-1,s+1,v); else { if(v<1)//否则向上或向下 { if(x-1>=0 && g[x-1][y]=='.') dfsu(x-1,y,s+1,v+1); if(x+1<n && g[x+1][y]=='.') dfsd(x+1,y,s+1,v+1); } return ; } } void dfsr(int x,int y,int s,int v) //向右。 { ans=max(ans,s); if(y+1<n && g[x][y+1]=='.') dfsr(x,y+1,s+1,v); else { if(v<1) { if(x-1>=0 && g[x-1][y]=='.') dfsu(x-1,y,s+1,v+1); if(x+1<n && g[x+1][y]=='.') dfsd(x+1,y,s+1,v+1); } return ; } } void dfsu(int x,int y,int s,int v) //向上。 { ans=max(ans,s); if(x-1>=0 && g[x-1][y]=='.') dfsu(x-1,y,s+1,v); else { if(v<1) { if(y-1>=0 && g[x][y-1]=='.') dfsl(x,y-1,s+1,v+1); if(y+1<n && g[x][y+1]=='.') dfsr(x,y+1,s+1,v+1); } return ; } } void dfsd(int x,int y,int s,int v) //向下。 { ans=max(ans,s); if(x+1<n && g[x+1][y]=='.') dfsd(x+1,y,s+1,v); else { if(v<1) { if(y-1>=0 && g[x][y-1]=='.') dfsl(x,y-1,s+1,v+1); if(y+1<n && g[x][y+1]=='.') dfsr(x,y+1,s+1,v+1); } return ; } } void dfslu(int x,int y,int s,int v) //向左上。 { ans=max(ans,s); if(x-1>=0 && y-1>=0 && g[x-1][y-1]=='.') dfslu(x-1,y-1,s+1,v); else { if(v<1) { if(x+1<n && y-1>=0 && g[x+1][y-1]=='.') dfsld(x+1,y-1,s+1,v+1); if(x-1>=0 && y+1<n && g[x-1][y+1]=='.') dfsru(x-1,y+1,s+1,v+1); } return ; } } void dfsrd(int x,int y,int s,int v) //向右下。 { ans=max(ans,s); if(x+1<n && y+1<n && g[x+1][y+1]=='.') dfsrd(x+1,y+1,s+1,v); else { if(v<1) { if(x+1<n && y-1>=0 && g[x+1][y-1]=='.') dfsld(x+1,y-1,s+1,v+1); if(x-1>=0 && y+1<n && g[x-1][y+1]=='.') dfsru(x-1,y+1,s+1,v+1); } return ; } } void dfsru(int x,int y,int s,int v) //向右上。 { ans=max(ans,s); if(x-1>=0 && y+1<n && g[x-1][y+1]=='.') dfsru(x-1,y+1,s+1,v); else { if(v<1) { if(x-1>=0 && y-1>=0 && g[x-1][y-1]=='.') dfslu(x-1,y-1,s+1,v+1); if(x+1<n && y+1<n && g[x+1][y+1]=='.') dfsrd(x+1,y+1,s+1,v+1); } return ; } } void dfsld(int x,int y,int s,int v) //向左下。 { ans=max(ans,s); if(x+1<n && y-1>=0 && g[x+1][y-1]=='.') dfsld(x+1,y-1,s+1,v); else { if(v<1) { if(x-1>=0 && y-1>=0 && g[x-1][y-1]=='.') dfslu(x-1,y-1,s+1,v+1); if(x+1<n && y+1<n && g[x+1][y+1]=='.') dfsrd(x+1,y+1,s+1,v+1); } return ; } } }; int main() { while(~scanf("%d",&n),n) { for(int i=0;i<n;i++) scanf("%s",g[i]); dfs q; ans=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(g[i][j]=='.') { if(j-1>=0 && g[i][j-1]=='.') q.dfsl(i,j-1,1,0); if(j+1<n && g[i][j+1]=='.') q.dfsr(i,j+1,1,0); if(i-1>=0 && g[i-1][j]=='.') q.dfsu(i-1,j,1,0); if(i+1<n && g[i+1][j]=='.') q.dfsd(i+1,j,1,0); if(i-1>=0 && j-1>=0 && g[i-1][j-1]=='.') q.dfslu(i-1,j-1,1,0); if(i+1<n && i+1<n && g[i+1][j+1]=='.') q.dfsrd(i+1,j+1,1,0); if(i+1<n && j-1>=0 && g[i+1][j-1]=='.') q.dfsld(i+1,j-1,1,0); if(i-1>=0 && j+1<n && g[i-1][j+1]=='.') q.dfsru(i-1,j+1,1,0); } } } printf("%d\n",ans+1); //ans+1.因为我没算起始点。 } return 0; }
HDU 5024 Wang Xifeng's Little Plot(2014广州网络赛1003)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。