首页 > 搜索 > DFS搜索 > HDU 2782-HOJ-The Worm Turns-DFS-[解题报告]C++
2014
02-14

HDU 2782-HOJ-The Worm Turns-DFS-[解题报告]C++

The Worm Turns

问题描述 :

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.

输入:

Input 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.

输出:

Input 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.

样例输入:

5 5 
3 
0 4 3 1 3 2 
0 0

样例输出:

Case 1: 22 0 3 W

时间4s~~~爆搜~~

#include <cstring>
#include <cstdio>
using namespace std;
int map[700][700];
int vis[700][700];
int ansx,ansy;
int ansd,anssum;
int n,m;
int res=0;
int xx[4]={0,-1,1,0};
int yy[4]={1,0,0,-1};
void dfs(int x,int y,int ans,int pre)
{
    if(pre==-1)
    {
        int i;
        for(i=0;i<4;i++)
        {
            int nx=x+xx[i];
            int ny=y+yy[i];
            if(nx<0||nx>=n||ny<0||ny>=m)
                continue;
            if(vis[nx][ny])
                continue;
            vis[nx][ny]=1;
            dfs(nx,ny,ans+1,i);
            vis[nx][ny]=0;
            if(res>anssum)
            {
                ansx=x;
                ansy=y;
                ansd=i;
                anssum=res;
            }
        }
        return ;
    }
    int i;
    int flag=1;
    int nx=x+xx[pre];
    int ny=y+yy[pre];
    if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny])
    {
        vis[nx][ny]=1;
        dfs(nx,ny,ans+1,pre);
        vis[nx][ny]=0;
        flag=0;
    }
    else
    {
        for(i=0;i<4;i++)
        {
            if(i==pre)
                continue;
            nx=x+xx[i];
            ny=y+yy[i];
            if(nx<0||nx>=n||ny<0||ny>=m)
                continue;
            if(vis[nx][ny])
                continue;
            vis[nx][ny]=1;
            dfs(nx,ny,ans+1,i);
            vis[nx][ny]=0;
            flag=0;
        }
    }
    if(flag)
    {
        if(res<ans)
            res=ans;
    }

}
int main()
{
    int cas=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cas++;
        if(n==0&&m==0)
            break;
        int r;
        scanf("%d",&r);
        int i;
        memset(vis,0,sizeof(vis));
        for(i=0;i<r;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            vis[x][y]=1;
        }
        int j;
        anssum=-1;
        res=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(!vis[i][j])
                {

                    vis[i][j]=1;
                    dfs(i,j,1,-1);
                    vis[i][j]=0;
                }

            }
        }
        printf("Case %d: %d %d %d ",cas,anssum,ansx,ansy);
        if(ansd==0)
            printf("E\n");
        else if(ansd==1)
            printf("N\n");
        else if(ansd==2)
            printf("S\n");
        else if(ansd==3)
            printf("W\n");

    }
}

解题参考:http://blog.csdn.net/juststeps/article/details/9397399


,
  1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮