QDUOJ 炸老师与他的女朋友们 bfs+状压

炸老师与他的女朋友们

Description

qdu最帅的炸老师今天又要抽空去找他的女朋友们了，但是考虑到他的好gay友ycb仍是个单身狗，炸老师作为基友不希望打击他。所以他在找女朋友们的路途中必须要避开ycb老师，可他又不知道ycb的具体位置，只知道一些可能的位置，所以他必须要避开所有这些位置，同时炸老师希望找完所有女朋友所用的时间最短，因为炸老师很忙的。

现在假定炸老师在一个n*m的矩阵中，'S'为炸老师的初始位置，'.'表示可以走，'#'表示ycb老师的可能位置，'*'表示炸老师所有女朋友的位置，炸老师每走一格需要花费一秒的时间，而且炸老师每次只能往上下左右四个方向走,请你帮炸老师计算一下他找完所有女朋友所需的最短时间（找完最后一个女朋友即可，无需回到出发点），由于炸老师非常特别无敌快，因此可以不考虑炸老师在女友家停留的时间。如果炸老师没有办法在避开ycb所有可能位置的条件下找完他的女朋友们,那么炸老师就不去了。

Input

输入包含多组测试样例 第一行输入两个整数n,m表示n行m列的矩阵（0<n,m<=30） 第二行到n+1行每行m个字符,含义如上题所述。(输入保证*的个数不会超过10个，毕竟炸老师的精力也是有限的)

Output

对于每组输出,输出只包含一个整数。如果炸老师可以找完他的女朋友们,则输出最短时间，如果炸老师不去了，那么输出-1.

Sample Input 1

7 13

*...........*

....#...#....

..#...#..#...

..#......#...

...#.S..#....

....#.#......

*....#......*

Sample Output 1

33

Sample Input 2

10 10

..........

..S.......

..........

..........

..........

.....#####

.....#....

.....#.*..

.....#....

.....#....

Sample Output 2

-1

Sample Input 3

3 7

.S...*.

.......

.*...*.

Sample Output 3

8

Hint

Source

六一八杯青岛大学首届编程大赛个人赛暨ACM集训队16级纳新

回顾acm纳新。小数据，一道经典的状压题。因为部分路径能够重复走，所以这里的b[x][y][sta]数组需要标记状态，sta每一位表示每个女朋友是否被访问到。只有在(x,y)走过且当前状态被标记过时，该点才不会继续加入队列。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<math.h>

#include<queue>

#include<stack>

#include<algorithm>

#define MAX 35

#define INF 0x3f3f3f3f

#define MOD 1000000007

using namespace std;

typedef long long ll;

char a[MAX][MAX];

int b[MAX][MAX][(<<)+],bb[MAX][MAX];

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

struct Node{

    int x,y,sta,s;

}node;

queue<Node> q;

int main()

{

    int n,m,c,bx,by,i,j;

    while(~scanf("%d%d",&n,&m)){

        c=;

        memset(bb,,sizeof(bb));

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

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

            for(j=;j<m;j++){

                if(a[i][j]=='*'){

                    bb[i][j]=c;

                    c++;

                }

                else if(a[i][j]=='S'){

                    bx=i;

                    by=j;

                }

            }

        }

        memset(b,,sizeof(b));

        while(q.size()){

            q.pop();

        }

        node.x=bx;

        node.y=by;

        node.sta=;

        node.s=;

        b[bx][by][]=;

        q.push(node);

        int f=-;

        while(q.size()){

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

                int tx=q.front().x+t[i][];

                int ty=q.front().y+t[i][];

                int sta=q.front().sta;

                int ss=q.front().s;

                if(tx<||ty<||tx>=n||ty>=m) continue;

                if(a[tx][ty]=='#') continue;

                if(a[tx][ty]=='*') sta|=<<bb[tx][ty];

                if(b[tx][ty][sta]==) continue;

                b[tx][ty][sta]=;

                if(sta==(<<c)-){

                    f=ss+;

                    break;

                }

                node.x=tx;

                node.y=ty;

                node.sta=sta;

                node.s=ss+;

                q.push(node);

            }

            q.pop();

            if(f>-) break;

        }

        if(f==-) printf("-1\n");

        else printf("%d\n",f);

    }

    return ;

}