poj1321+poj2251

心已赠人 2022-05-30 04:08 190阅读 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;
    }