首页 > 代码库 > HDU 2782 The Worm Turns (DFS)
HDU 2782 The Worm Turns (DFS)
Winston the Worm just woke up in a fresh rectangular patch of earth. The rectangular patch is divided into cells, and each cell contains either food or a rock. Winston wanders aimlessly for a while until he gets hungry; then he immediately eats the food in his cell, chooses one of the four directions (north, south, east, or west) and crawls in a straight line for as long as he can see food in the cell in front of him. If he sees a rock directly ahead of him, or sees a cell where he has already eaten the food, or sees an edge of the rectangular patch, he turns left or right and once again travels as far as he can in a straight line, eating food. He never revisits a cell. After some time he reaches a point where he can go no further so Winston stops, burps and takes a nap.
For instance, suppose Winston wakes up in the following patch of earth (X‘s represent stones, all other cells contain food):
If Winston starts eating in row 0, column 3, he might pursue the following path (numbers represent order of visitation):
In this case, he chose his path very wisely: every piece of food got eaten. Your task is to help Winston determine where he should begin eating so that his path will visit as many food cells as possible.
For instance, suppose Winston wakes up in the following patch of earth (X‘s represent stones, all other cells contain food):
If Winston starts eating in row 0, column 3, he might pursue the following path (numbers represent order of visitation):
In this case, he chose his path very wisely: every piece of food got eaten. Your task is to help Winston determine where he should begin eating so that his path will visit as many food cells as possible.
InputInput will consist of multiple test cases. Each test case begins with two positive integers, m and n , defining the number of rows and columns of the patch of earth. Rows and columns are numbered starting at 0, as in the figures above. Following these is a non-negative integer r indicating the number of rocks, followed by a list of 2r integers denoting the row and column number of each rock. The last test case is followed by a pair of zeros. This should not be processed. The value m×n will not exceed 625.OutputFor each test case, print the test case number (beginning with 1), followed by four values:
amount row column direction
where amount is the maximum number of pieces of food that Winston is able to eat, (row, column) is the starting location of a path that enables Winston to consume this much food, and direction is one of E, N, S, W, indicating the initial direction in which Winston starts to move along this path. If there is more than one starting location, choose the one that is lexicographically least in terms of row and column numbers. If there are optimal paths with the same starting location and different starting directions, choose the first valid one in the list E, N, S, W. Assume there is always at least one piece of food adjacent to Winston‘s initial position.Sample Input
5 5 3 0 4 3 1 3 2 0 0Sample Output
Case 1: 22 0 3 W
分析
题目大意就是给你一个地图，地图中只有两种元素，墙跟平地，然后要你求出一个人能在这个地图中走的最大距离。这个人一旦开始走路，那么他走的方向将是不变的。除非遇到墙，或者遇到地图的边，亦或者那个格子已经走过了，这个时候这个人才开始更换方向。
然后要你求出这个人能走的最大距离的起始点的位置，输出最大距离，起始点坐标，还有一开始走的方向。（E,N,S,W）,如果最大距离相同，那么要输出起始点坐标的字典序最小的那个。
还有，如果四个方向都能达到最大，那么选择的方向的优先级由（E,N,S,W）往下排列。
就是爆搜，题目给的时间很大。我们可以枚举起点，对于每一个点搜索。关于输出，在搜索时按（E,N,S,W）的顺序，在更新答案时，只有当前答案大于记录答案才更新。
#include <cstdio> #include <iostream> #include <cmath> #include <queue> #include <algorithm> #include <cstring> #include <climits> #define MAXN 626 #define X rx+dx[i] #define Y ry+dy[i] using namespace std; int t=0; int r,m,n,g[MAXN][MAXN],ans[MAXN][MAXN],sx,sy,step,ansdd,ansx,ansy,md,maxx; int ansd[MAXN][MAXN]; int dx[5]={0,0,-1,1,0}, dy[5]={0,1,0,0,-1}; void dfs(int x,int y) { for(int i=1;i<=4;i++) { int rx=x,ry=y; if(X>=0&&X<n&&Y>=0&&Y<m&&g[X][Y]==0) { if(x==sx&&y==sy) md=i; g[X][Y]=++step; if(step>ans[sx][sy]) ans[sx][sy]=step, ansd[sx][sy]=md; rx+=dx[i];ry+=dy[i]; while(X>=0&&X<n&&Y>=0&&Y<m&&g[X][Y]==0) { g[X][Y]=++step; if(step>ans[sx][sy]) ans[sx][sy]=step, ansd[sx][sy]=md; rx+=dx[i];ry+=dy[i]; } dfs(rx,ry); while(rx!=x||ry!=y) { g[rx][ry]=0; step--; rx-=dx[i];ry-=dy[i]; } } } } void init() { memset(g,0,sizeof(g)); memset(ans,0,sizeof(ans)); memset(ansd,0,sizeof(ansd)); ansdd=ansx=ansy=md=maxx=0; } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); while(1) { init(); ++t; scanf("%d%d",&n,&m); if(n==0&&m==0)return 0; scanf("%d",&r); for(int i=1;i<=r;i++) { int x,y; scanf("%d%d",&x,&y); g[x][y]=-1; } for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]!=-1) { step=0;sx=i;sy=j; g[sx][sy]=-1; dfs(sx,sy); g[sx][sy]=0; } for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(ans[i][j]>maxx) { maxx=ans[i][j]; ansx=i;ansy=j; ansdd=ansd[i][j]; } printf("Case %d: %d %d %d ",t,maxx+1,ansx,ansy); if(ansdd==1) printf("E\n"); else if(ansdd==2) printf("N\n"); else if(ansdd==3) printf("S\n"); else if(ansdd==4) printf("W\n"); } return 0; }
HDU 2782 The Worm Turns (DFS)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。