WUST 1482 find clouds（bfs+状态压缩）

亦凉 2022-06-13 11:46 199阅读 0赞

## 1482: find clouds ##

Time Limit: 3 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 69 Accepted: 14  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

公主生气了，现在wh需要集齐 X 种云（帽子云，波浪云。。。）让公主开心。开始wh在一个迷宫的入口处，迷宫里恰好有 X 种云，每种云恰好只有一个。

wh每一步可以向上，向下，向左，向右走一步。请帮助wh计算最少需要走多少步收集到所有的云朵。由于wh有特殊 的技能，所以不用考虑wh该怎么走出去~

## Input ##

第一行 n,m,k,迷宫有n行,m列,里面有 k 种云朵。接下来有n行，每行有m个字符。字符只包括 '.' , '\#' , 's'和数字xi(1<=i<=k，0<=xi<k)。

'.'表示wh可以走到当前位置，'\#'表示该位置不可达,'S'表示迷宫的入口，数字xi表 示这个位置是第i种云朵。迷宫的边缘部分全部是'\#',只有一个入口。

(10<=n,m<=100,0<=k<=10)

## Output ##

; 若可以收齐所有的云朵，输出最少的步数。否则输出 "bengkala".

## Sample Input ![copy.gif][] ##

10 10 
    2
    ##########
    #.####.0.#
    #..#.....#
    #.#1..##.#
    #.#.#....#
    #......#.#
    #.S#.#..##
    #.#.#....#
    #...######
    ##########

##     ##

## Sample Output ##

题解：

这题不想吐槽了，同样的代码交了3遍，前两遍tle，第三遍ac了。。。还拿小号做了n次实验。。不得不说这是一道人品题（或许是我太弱了，想不出更好的方法）。。给的测试数据小就过得快，而且这题还搜不到题解对不对（手动滑稽）,毕竟这是我们学校acm原创题，为了造福后人，写一个题解吧，这题算是搜索入门和进阶之间的题目吧，要有一定基础才能做出来，重点就是状态的保存，因为只有有钥匙和没钥匙（云就叫钥匙吧，大多数题都是以钥匙出现）两种状态，我们用二进制保存，每一位1和0就是当前钥匙有和无，假如要有k把钥匙，那么需要的内存为1<<k，每一次bfs，获得当前节点状态key，那么怎么获得钥匙情况呢，就拿当前地图的钥匙情况与key做&运算（有点难理解，理解一下），假如当前钥匙没有取，就把key的状态做|运算（理解啊理解）,只要会了状态压缩，那么这题就简单了

ps：

手动赋值p数组超时了n次，改成memset就过了。。好迷啊

下面是代码：

#include<stdio.h>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    using namespace std;
    struct node
    {
        int x,y;
        int step;//保存步数
        int key;//保存钥匙情况
        int num;//保存当前钥匙数目
    };
    int p[101][101][1025];//三维数组储存状态
    int dirx[4]={0,0,-1,1};
    int diry[4]={-1,1,0,0};//方向数组
    char s[105][105];//存图
    int n,m,k,stx,sty;
    queue<node>q;
    int main()
    {
        int i,j,r,w,xx,yy,tag;
        node now,next;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(p,0,sizeof(p));
            scanf("%d",&k);
            tag=0;
            for(i=0;i<n;i++)
            {
                scanf("%s",s[i]);
                if(!tag)
                for(j=0;j<m;j++)
                {
                    if(s[i][j]=='S')//保存初始位置
                    {
                        stx=i;
                        sty=j;
                        tag=1;
                    }
                }
            }
            if(k==0)
            {
                printf("0\n");
                continue;
            }
            while(!q.empty())q.pop();
            now.x=stx;
            now.y=sty;
            now.step=0;
            now.key=0;
            now.num=0;
            p[stx][sty][0]=1;
            q.push(now);
            w=-1;//纪录如果可达的步数
            while(!q.empty())//bfs
            {
                now=q.front();
                q.pop();
                for(i=0;i<4;i++)
                {
                    xx=now.x+dirx[i];
                    yy=now.y+diry[i];
                    int key=now.key;
                    next.num=now.num;
                    if(xx<0||yy<0||xx>=n||yy>=m||s[xx][yy]=='#')
                        continue;
                    if(s[xx][yy]>='0'&&s[xx][yy]<='9')//获得钥匙状态，是否取了当前的钥匙
                    {
                        int add=s[xx][yy]-'0';
                        if(key&(1<<add))//重点理解！！！
                            continue;
                        else
                            key=key|(1<<add);//重点理解！！！
                        next.num++;
                    }
                    if(!p[xx][yy][key])//当前状态没被覆盖
                    {
                        next.x=xx;
                        next.y=yy;
                        next.key=key;
                        next.step=now.step+1;
                        if(next.num>=k)//找到了立即退出
                        {
                            w=next.step;
                            goto loop;
                        }
                        q.push(next);
                        p[xx][yy][key]=1;
                    }
                }
            }
            loop:;
            if(w==-1)
            {
                printf("bengkala\n");
            }
            else
                printf("%d\n",w);
            }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1482&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1482&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1482&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif