hdoj 1885 Key Task 【BFS+状态压缩】

怼烎@ 2022-08-13 11:28 162阅读 0赞

题目：[hdoj 1885 Key Task][]

题意：给出一些点，然后有一些钥匙和门，钥匙拿到才可以打开门，问到出口的最短时间。

分析：很明显的广搜 + 状态压缩题目。

坑点：

1：题目没读清楚，以为要把所有的们打开才能出去。

AC代码：

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #include <string>
    
    using namespace std;
    typedef long long LL;
    const int N = 120;
    
    char mp[N][N];
    int n,m;
    struct Node
    {
        int x,y;
        int flag , step;
    };
    int vis[N][N][1<<5];
    int dx[5]={0,0,1,-1};
    int dy[5]={1,-1,0,0};
    void print()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                printf("%c ",mp[i][j]);
            puts("");
        }
    }
    int BFS(Node s,int ok)
    {
        //print();
        //printf("%d\n",ok);
        memset(vis,0,sizeof(vis));
        s.step = 0;s.flag = 0;
        queue<Node> q;
        q.push(s);
        vis[s.x][s.y][s.flag] = 1;
        mp[s.x][s.y] = '.';
        while(!q.empty())
        {
            Node u = q.front() ;
            q.pop();
            if( mp[u.x][u.y]=='X')
                return u.step;
            for(int i=0;i<4;i++)
            {
                Node f = u;
                f.x+=dx[i];
                f.y+=dy[i];
                f.step++;
                if(vis[f.x][f.y][f.flag]==1 || f.x<0 || f.y<0 || f.x>=n || f.y>=m || mp[f.x][f.y]=='#')
                    continue;
                if(mp[f.x][f.y]>='5'&& mp[f.x][f.y]<='8')
                {
                    f.flag |= (1<<(mp[f.x][f.y]-'5'));
                    q.push(f);
                    vis[f.x][f.y][f.flag] = 1;
                }
                else if(mp[f.x][f.y]>='0' && mp[f.x][f.y]<='3')
                {
                    int css = mp[f.x][f.y]-'0';
                    if(f.flag & (1<<css))
                    {
                        q.push(f);
                        vis[f.x][f.y][f.flag] = 1;
                    }
                }
                else
                {
                    q.push(f);
                    vis[f.x][f.y][f.flag] = 1;
                }
            }
        }
        return -1;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        while(~scanf("%d%d",&n,&m) && m+n)
        {
            Node s;
            int ok = 0;
            for(int i=0;i<n;i++)
            {
                getchar();
                for(int j=0;j<m;j++){
                    scanf("%c",&mp[i][j]);
                    if(mp[i][j]=='*')
                        s.x=i,s.y=j;
                    if(mp[i][j]=='B')
                        mp[i][j] = '0';
                    else if(mp[i][j]=='Y')
                        mp[i][j] = '1';
                    else if(mp[i][j]=='R')
                        mp[i][j] = '2';
                    else if(mp[i][j]=='G')
                        mp[i][j] = '3';
                    else if(mp[i][j]=='b')
                        mp[i][j] = '5';
                    else if(mp[i][j]=='y')
                        mp[i][j] = '6';
                    else if(mp[i][j]=='r')
                        mp[i][j] = '7';
                    else if(mp[i][j]=='g')
                        mp[i][j] = '8';
                    if(mp[i][j]>='0' && mp[i][j]<='3')
                        ok|=(1<<(mp[i][j]-'0'));
                }
            }
            int ans = BFS(s,ok);
            if(ans == -1)
                printf("The poor student is trapped!\n");
            else
                printf("Escape possible in %d steps.\n",ans);
        }
        return 0;
    }

[hdoj 1885 Key Task]: http://acm.hdu.edu.cn/showproblem.php?pid=1885