poj1321+poj2251-蒲公英云

poj1321+poj2251

心已赠人 2022-05-30 04:08 249阅读 0赞

poj1321代码实现（dfs）：

#include <iostream>
#include <string.h>
using namespace std;
int n,k;
char str[10][10];
int flag[10];
int sum;
void dfs(int i)
{
    if(i>n)
        return;
    int temp=0;
    //cout<<"flag"<<endl;
    for(int t=0; t<n; t++)
    {
        //cout<<flag[t]<<endl;
        temp+=flag[t];
    }
    if(temp==k)
    {
        sum++;
        //cout<<"sum==   "<<sum<<endl;
        return;
    }
    for(int j=0; j<n; j++)
    {
        if(str[i][j]=='#' && flag[j]==0)
        {
            flag[j]=1;
            dfs(i+1);
            flag[j]=0;
        }
    }
    dfs(i+1);
}
int main()
{
    while(cin>>n>>k)
    {
        if(n==-1 && k==-1)
        {
            break;
        }
        memset(str,0,sizeof(str));
        memset(flag,0,sizeof(flag));
        for(int i=0; i<n; i++)
        {
            cin>>str[i];
        }
        /*for(int i=0;i<n;i++)
        {
            cout<<str[i]<<endl;
        }*/
        sum=0;
        dfs(0);
        cout<<sum<<endl;
    }
    return 0;
}

poj2251（bfs）：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=35;
const int INF=1000000;
int L,R,C;
char str[maxn][maxn][maxn];
int x[6]= { 0, 0, 0, 0, 1,-1};
int y[6]= { 0, 0, 1,-1, 0, 0};
int z[6]= {-1, 1, 0, 0, 0, 0};
struct node
{
    int i,j,k;
    int dis;
};
queue<node>que;
int bfs(node a)
{
    que.push(a);
    str[a.i][a.j][a.k]='#';
    while(!que.empty())
    {
        node ah=que.front();
        que.pop();
        if(str[ah.i][ah.j][ah.k]=='E')
        {
            return ah.dis;
        }
        node aa1;
        for(int t=0; t<6; t++)
        {
            int ih=ah.i+x[t];
            int jh=ah.j+y[t];
            int kh=ah.k+z[t];
            if(str[ih][jh][kh]!='#' && 0<=ih && ih<L && 0<=jh && jh<R && 0<=kh && kh<C  )
            {
                if(str[ih][jh][kh]!='E')
                str[ih][jh][kh]='#';
                aa1.i=ih;
                aa1.j=jh;
                aa1.k=kh;
                aa1.dis=ah.dis+1;
                que.push(aa1);
            }
        }
    }
    return INF;
}
int main()
{
    while(cin>>L>>R>>C)
    {
        if(L==0 && R==0 && C==0)
        {
            break;
        }
        memset(str,0,sizeof(str));
        for(int i=0; i<L; i++)
        {
            for(int j=0; j<R; j++)
            {
                cin>>str[i][j];
            }
        }
        while(que.size()!=0)
            que.pop();
        node a1;
        for(int i=0; i<L; i++)
        {
            for(int j=0; j<R; j++)
            {
                for(int k=0; k<C; k++)
                {
                    if(str[i][j][k]=='S')
                    {
                        a1.i=i;
                        a1.j=j;
                        a1.k=k;
                        a1.dis=0;
                    }
                }
            }
        }
        int kkkk=bfs(a1);
        if(kkkk!=INF)
        {
            cout<<"Escaped in "<<kkkk<<" minute(s)."<<endl;
        }
        else
        {
            cout<<"Trapped!"<<endl;
        }
    }
    return 0;
}