HDU 1010 Tempter of the Bone(dfs)

怼烎@ 2022-07-15 10:39 117阅读 0赞

题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题意：能否正好花费T时间从点S到点D

奇偶剪枝：

是数据结构的搜索中，剪枝的一种特殊小技巧。

现假设起点为(sx,sy)，终点为（ex,ey），给定t步恰好走到终点，

如图所示（“|”竖走，“—”横走，“+”转弯），易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下，起点到终点的最短步数，记做step，此处step1=8；

如图，为一般情况下非最短路径的任意走法举例，step2=14；

step2-step1=6，偏移路径为6，偶数（易证）；

故，若t-\[abs(ex-sx)+abs(ey-sy)\]结果为非偶数（奇数），则无法在t步恰好到达；

返回，false；

反之亦反。（引用某大神博客http://www.cnblogs.com/zhourongqing/archive/2012/04/28/2475684.html）

code：

#include<stdio.h>
    #include<string>
    #include<string.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    int vis[10][10];
    int dx[]={-1,1,0,0};//上下左右 
    int dy[]={0,0,-1,1};
    int n,m,k,sx,sy,ex,ey,flag;
    char map[10][10];
    void dfs(int x,int y,int sec)
    {
    	if(flag)
    		return ;
    	if(sec==k&&map[x][y]=='D')
    	{
    		flag=1;
    		return ;
    	}
    	if(sec==k)
    		return ;
    	if(vis[x][y]||x<=0||y<=0||x>n||y>m||map[x][y]=='#')
    		return ;
    	vis[x][y]=1;
    	for(int i=0;i<4;i++)
    		dfs(x+dx[i],y+dy[i],sec+1);
    	vis[x][y]=0;
    	return ;
    }
    int main()
    {
    	while(cin>>n>>m>>k,n,m,k)
    	{
    		memset(map,0,sizeof(map));
    		memset(vis,0,sizeof(vis));
    		flag=0;
    		for(int i=1;i<=n;i++)
    		{
    			getchar();
    			for(int j=1;j<=m;j++)
    			{
    				scanf("%c",&map[i][j]);
    				if(map[i][j]=='X')
    					vis[i][j]=1;
    				if(map[i][j]=='S')
    					{sx=i;sy=j;}
    				if(map[i][j]=='D')
    					{ex=i;ey=j;}
    			}
    		}
    		getchar();
    		if(abs(sx-ex)+abs(sy-ey)>k||(sx+ex+sy+ey+k)%2==1)
    		{
    			printf("NO\n");
    			continue;
    		}
    		dfs(sx,sy,0);
    		if(flag)
    			cout<<"YES"<<endl;
    		else
    			cout<<"NO"<<endl;
    	}
    	return 0;
    }

题目给了1000ms，我的代码900ms险过，还需优化

百度代码400ms思路与我差不多：

#include<iostream>
    #include<math.h>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    char s[10][10];
    int ax,ay,bx,by,n,m,k;
    int t[4][2]={1,0,-1,0,0,1,0,-1},vist[10][10],flag;
    void dfs(int x,int y,int count)
    {
        int i,mx,my;
        if(x==bx&&y==by)
        {
            if(k==count)
                flag=1;
            return;
        }
        if(count>=k)
            return;
        if(s[x][y]!='X')
        {
            for(i=0;i<4;i++)
            {
                mx=x+t[i][0];
                my=y+t[i][1];
                if(s[mx][my]!='X'&&mx>=1&&mx<=n&&my>=1&&my<=m&&!vist[mx][my])
                {
                    vist[mx][my]=1;
                    dfs(mx,my,count+1);
                    vist[mx][my]=0;
                    if(flag)                       //注意，在找到了目标之后，就不需要再找！以往编写dfs时，没有注意这点
                        return;
                }
            }
        }
    }
    int main()
    {
        while(scanf("%d%d%d",&n,&m,&k)>0&&(n+m+k))
        {
            int i,count;
            for(i=1;i<=n;i++)
            {
                getchar();
                for(int j=1;j<=m;j++)
                {
                    scanf("%c",&s[i][j]);
                    if(s[i][j]=='S')
                    {
                        ax=i;
                        ay=j;
                    }
                    if(s[i][j]=='D')
                    {
                        bx=i;
                        by=j;
                    }
                }
            }
            getchar();
            memset(vist,0,sizeof(vist));
            if(abs(ax-bx)+abs(ay-by)>k||(ax+bx+ay+by+k)%2==1)            //剪枝
            {
                printf("NO\n");
                continue;
            }
            vist[ax][ay]=1;
            flag=0;
            count=0;
            dfs(ax,ay,count);
            if(flag==1)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }