Poj 3087 + Hdu 1312 + Hdu 1241 + Poj 3278 (基础BFS DFS)

布满荆棘的人生 2022-09-20 15:01 256阅读 0赞

DFS的剪枝真的很重要，还需要多加练习！

**Poj 3087 Shuffle'm Up**

其实是一道模拟题，被别人分类到了搜索里……

题意：  
给你两堆纸牌，让你通过数次洗牌动作使得洗牌之后的序列为给定序列。输出最小的洗牌次数。  
洗牌方法：  
把第二堆的第一张放在最下面，让后放第一堆最下面的那张，；轮流放。  
洗完之后，把下面的n张作为第一堆，上面的n张作为第二堆。

#include <cstdio>
    #include <cstring>
    
    const int N=105;
    
    char s1[N],s2[N],result[2*N],source[2*N],temp[2*N];
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
    	{
    	    int i,j,k,n;
            scanf("%d",&n);
            scanf("%s%s%s",s1,s2,result);
    
            strcpy(source,s1);
            strcat(source,s2);
            strcpy(temp,source);
    
            for (k=0;strcmp(temp,result)!=0;k++)
            {
                for (j=0;j<n;j++)
                    s2[j]=temp[j];
                for (i=0;i<n;i++,j++)
                    s1[i]=temp[j];
                for (i=0,j=0;i<n;i++,j++)
                {
                    temp[j++]=s1[i];
                    temp[j]=s2[i];
                }
                if (strcmp(temp,source)==0) //回到初始,构成循环
                {
                    k=-1;
                    break;
                }
            }
            printf("%d %d\n",Cas,k);
    	}
        return 0;
    }

**Hdu 1312 Red and Black**

简单题

题意：给一个地图，‘.'表示可走的点，‘\#’表示不可走的点，‘@’表示起点；求：可以走几个点，包括起点

#include <cstdio>
    
    const int N=25;
    
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n,cnt;
    char g[N][N];
    
    void DFS (int u,int v)
    {
        g[u][v]='*';
        for (int i=0;i<4;i++)
        {
            int x=u+dx[i];
            int y=v+dy[i];
            if (x>=0 && x<m && y>=0 && y<n && g[x][y]=='.')
            {
                g[x][y]='*';
                cnt++;
                DFS(x,y);
            }
        }
    }
    
    int main ()
    {
        while (scanf("%d%d",&n,&m),m)
        {
            int sx,sy;
            for (int i=0;i<m;i++)
            {
                scanf("%s",g[i]);
                for (int j=0;j<n;j++)
                    if (g[i][j]=='@')
                        sx=i,sy=j;
            }
            cnt=1;
            DFS(sx,sy);
            printf("%d\n",cnt);
        }
        return 0;
    }

**Hdu 1241 Oil Deposits**

题意：一块油田。@代表有油，\*代表没油。求8个方向连通的油田共有多少块

#include <cstdio>
    
    const int N=105;
    
    int dx[8]={-1,-1,-1,0,0,1,1,1};
    int dy[8]={-1,0,1,-1,1,-1,0,1};
    int m,n;
    char g[N][N];
    
    void DFS (int u,int v)
    {
        g[u][v]='*';
        for (int i=0;i<8;i++)
        {
            int x=u+dx[i];
            int y=v+dy[i];
            if (x>=0 && x<m && y>=0 && y<n && g[x][y]=='@')
            {
                g[x][y]='*';
                DFS(x,y);
            }
        }
    }
    
    int main ()
    {
        while (scanf("%d%d",&m,&n),m)
        {
            int cnt=0,i;
            for (i=0;i<m;i++)
                scanf("%s",g[i]);
            for (i=0;i<m;i++) for (int j=0;j<n;j++)
                if (g[i][j]=='@')
                {
                    DFS(i,j);
                    cnt++;
                }
            printf("%d\n",cnt);
        }
        return 0;
    }

**Poj 3278 Catch That Cow**

很经典的一类题目

题意：给定两个整数n和k，通过 n+1或n-1 或n\*2 这3种操作，使得n==k，输出最少的操作次数

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    int start,end;
    bool visit[100050];
    
    struct Node
    {
    	int x,step;
    };
    
    int Deal (int a,int b)
    {
    	switch (b)
    	{
    	case 0:return a-1;
    	case 1:return a+1;
    	case 2:return a*2;
    	}
    }
    
    int BFS ()
    {
    	visit[start]=true;
    	queue <Node> Q;
    	Node s,e;
    	s.x=start;
    	s.step=0;
    	Q.push(s);
    	while (Q.empty()==false)
    	{
    	    s=Q.front();
    	    Q.pop();
    		if (s.x==end)
    			break;
    		for (int i=0;i<3;i++)
    		{
    			e.x=Deal(s.x,i);
    			e.step=s.step+1;
    			if (e.x>=0 && e.x<=100000 && visit[e.x]==false)
    			{
    				Q.push(e);
    				visit[e.x]=true;
    			}
    		}
    	}
    	return s.step;
    }
    
    int main ()
    {
    	scanf("%d%d",&start,&end);
    	memset(visit,false,sizeof(visit));
    	printf("%d\n",BFS());
    	return 0;
    }