ACM 深搜 Seeding&Tempter of the Bone

我就是我 2022-06-12 05:37 152阅读 0赞

暑期集训开始啦~因为是第一天，所以还没有正式开始讲座什么的，下午是一个小训练。

题目主要是深搜广搜，难度不大，但是我为了以后日更垫个底，先更两题深搜压压惊~

**ZOJ 2100 Seeding**

![20170717093703001][]

![20170717093730453][]

题目大意：S是不能走得，剩下的.要一笔画完，问是否可以实现。

我的思路：一本正经的深搜啊，都写在备注里啦~

#include <stdio.h>
    char a[10][10];
    int n,m,i,j,z[4][2]={0,1,0,-1,1,0,-1,0},re,sum;//四个方向 
    void dfs(int x,int y,int ss)
    {
    	if(x>=n||y>=m||x<0||y<0)return;//出界 
    	int i,xx,yy;
    	for(i=0;i<4;i++)
    	{
    		xx=x+z[i][0];
    		yy=y+z[i][1];
    		if(a[xx][yy]!='S')
    		{
    			if(ss==n*m-sum-1)//走完啦~ 
    			{re=1;return;}
    			a[xx][yy]='S';//标记 
    			dfs(xx,yy,ss+1);
    			a[xx][yy]='.';//复原，方便下次深搜 
    		}
    	}
    	return;
    }
    int main()
    {	
    	while(scanf("%d%d",&n,&m))
    	{
    		sum=0;
    		if(n==0&&m==0)break;
    		for(i=0;i<n;i++)
    		{
    			scanf("%s",a[i]);
    			for(j=0;j<m;j++)
    			{
    				if(a[i][j]=='S')
    				sum++;
    			}
    		}
    		a[0][0]='S';
    		re=0;
    		dfs(0,0,0);		
    		if(re)printf("YES\n");
    		else printf("NO\n");
    	}
    }

**ZOJ 2110 Tempter of the Bone**  
![20170717095042830][]

![20170717095047011][]

题目大意：（参照样例一）给出4\*4的地图，从S走到D，5步是否恰好可以，是正好五步，所以可以绕完为了满足这个5的哦。

我的思路：还是 一本正经 的 深搜呀...不过这里剪枝了一下，更快一些，深搜的函数里也可以剪。

#include <stdio.h>
    char a[10][10];
    int n,m,s,i,j,z[4][2]={0,1,0,-1,1,0,-1,0},sx,sy,dx,dy,wall,re;//四个方向 
    void dfs(int x,int y,int ss)
    {
    	if(x>=n||y>=m||x<0||y<0)return;//出界 
    	if(ss==s&&x==dx&&y==dy)	re=1;//走到目的地 
    	if(re)return;
    	int i,xx,yy;
    	for(i=0;i<4;i++)
    	{
    		xx=x+z[i][0];
    		yy=y+z[i][1];
    		if(a[xx][yy]!='X')
    		{
    			a[xx][yy]='X';//标记 
    			dfs(xx,yy,ss+1);
    			a[xx][yy]='.';//复原 
    		}
    	}
    	return;
    }
    int main()
    {	
    	while(scanf("%d%d%d",&n,&m,&s))
    	{
    		wall=0;
    		if(n==0&&m==0&&s==0)break;
    		for(i=0;i<n;i++)
    		{
    			scanf("%s",a[i]);
    			for(j=0;j<m;j++)
    			{				
    				if(a[i][j]=='S')
    				sx=i,sy=j;
    				if(a[i][j]=='D')
    				dx=i,dy=j;
    				if(a[i][j]=='X')
        			wall++;
    			}
    					
    		}
    		if(n*m-wall<=s)
            {
                printf("NO\n");
    			continue;
            }
    		a[sx][sy]='X';
    		re=0;
    		dfs(sx,sy,0);		
    		if(re)printf("YES\n");
    		else printf("NO\n");
    	}
    }

[20170717093703001]: /images/20220612/ca42f930ab4b4209b5ef1d48b16b1f74.png
[20170717093730453]: /images/20220612/09f377657d29420f9de39e5bba6b7b01.png
[20170717095042830]: /images/20220612/8a1b5fa683ff44abb2be82f289b5600d.png
[20170717095047011]: /images/20220612/2cb762c9517a4f9c990cb7a4730e4fa8.png