ACM搜索问题盘点

时间：2021-01-19 17:04:41

深度搜索：棋盘问题，详见http://poj.org/problem?id=1321

ACM搜索问题盘点

//#include<bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<queue>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

char a[10][10];

int vis[10];

int n,k;

int ans,now;

void DFS(int m)

{

	if(now==k){

		ans++;

		return ;

	}

	if(m==n)

		return ;

	for(int i=0;i<n;i++){

		if(!vis[i]&&a[m][i]=='#')

		{

			vis[i]=1;

			now++;

			DFS(m+1);

			vis[i]=0;

			now--;

		}

	}

	DFS(m+1);

}

int main()

{

	while(scanf("%d%d",&n,&k)&&n!=-1&&k!=-1)

	{

		memset(vis,0,sizeof(vis));

		for(int i=0;i<n;i++)

			scanf("%s",a[i]);

		ans=now=0;

		DFS(0);

		printf("%d\n",ans);

	}

}

　

BFS题目：Dungeon Master  (POJ2251： http://poj.org/problem?id=2251)

ACM搜索问题盘点

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<queue>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

int L,R,C;

char Map[][][];

int vis[][][];

int to[][]={,,,,,-,,,,,-,,,,,-,,};

int sx,sy,sz,ex,ey,ez;

int ans;

struct node{

    int x;

    int y;

    int z;

    int step;

};

int check(int x,int y,int z)

{

    if(x<||y<||z<||x>=L||y>=R||z>=C)

        return ;

    else if(Map[x][y][z]=='#')

            return ;

    else if(vis[x][y][z]==)

        return ;

    return ;

}

int bfs()

{

    queue<node> q;

    node temp,next;

    while(!q.empty())

    {

        q.pop();

    }

    temp.x=sx;

    temp.y=sy;

    temp.z=sz;

    temp.step=;

    q.push(temp);

    while(!q.empty())

    {

        temp=q.front();

        q.pop();

        if(temp.x==ex&&temp.y==ey&&temp.z==ez)

        {

            return temp.step;

        }

        for(int i=;i<;i++)

        {

            next=temp;

            next.x = temp.x+to[i][];

            next.y = temp.y+to[i][];

            next.z = temp.z+to[i][];

            if(check(next.x,next.y,next.z))

                continue;

            vis[next.x][next.y][next.z] = ;

            next.step = temp.step+;

            q.push(next);

        }

    }

    return ;

}

int main()

{

    while(scanf("%d%d%d",&L,&R,&C)&&L!=&&R!=&&C!=)

    {

        for(int i=;i<L;i++)

            for(int j=;j<R;j++)

            {

                scanf("%s",Map[i][j]);

                for(int k=;k<C;k++)

                {

                    if(Map[i][j][k]=='S')

                    {

                        sx=i;

                        sy=j;

                        sz=k;

                    }

                    else if(Map[i][j][k]=='E')

                    {

                        ex=i;

                        ey=j;

                        ez=k;

                    }

                }

            }

        memset(vis,,sizeof(vis));

        ans=;

        ans=bfs();

        if(ans)

            printf("Escaped in %d minute(s).\n",ans);

        else

            printf("Trapped!\n");

    }

}

Catch That Cow ：http://poj.org/problem?id=3278

ACM搜索问题盘点

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<queue>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

int N,K;

int ans;

int vis[];

struct node

{

    int value;

    int step;

};

int bfs()

{

    node temp,next;

    queue<node> q;

    temp.value=N;

    temp.step=;

    vis[temp.value]=;

    q.push(temp);

    while(!q.empty())

    {

        temp=q.front();

    //    cout<<temp.value<<endl;

        q.pop();

        if(temp.value==K)

            return temp.step;

        next=temp;

        for(int i=;i<;i++)

        {

            if(i==)

            {

                next.value=temp.value-;

            }

            if(i==)

            {

                next.value=temp.value+;

            }

            if(i==)

            {

                next.value=temp.value*;

            }

            if(next.value<||next.value>)

                continue;

            if(!vis[next.value])

            {

            //    cout<<1<<endl;

                vis[next.value]=;

                next.step=temp.step+;

                q.push(next);

            }

        }

    }

    return ;

}

int main()

{

    while(scanf("%d%d",&N,&K))

    {

        memset(vis,,sizeof(vis));

        ans=;

        ans=bfs();

        if(N>=K)

            printf("%d\n",N-K);

        else

            printf("%d\n",ans);

    }

    return ;

}

相关文章