QDUOJ 来自xjy的签到题（bfs+状压dp）

来自xjy的签到题

Description

爱丽丝冒险来到了红皇后一个n*n大小的花园，每个格子由'.'或'#'表示，'.'表示爱丽丝可以到达这个格子，‘#’表示爱丽丝不能到达这个格子，爱丽丝每1分钟可以移动到非'#'的相邻格子（与当前所在格子具有公共边）。花园下面有m个隧道，每个隧道有一个出口和一个入口。当爱丽丝到达隧道的入口时，她可以选择（也可以不选择）进入隧道入口，并通过隧道一次，然后立即（不花费时间）出现在隧道出口。爱丽丝一开始可以降临在花园的任何地方。有好奇心的爱丽丝想知道，她通过所有隧道且每个隧道仅通过一次最少需要花费多少时间。（注意，爱丽丝不能从隧道出口通往隧道入口）

Input

输入包含多个测试用例，不超过10组。对于每个测试用例，第一行输入n（1<=n<=15)和m(1<=m<=15)，分别表示地图的大小为n*n和m个隧道。然后给出一个n行n列的花园地图，由'.'或'#'组成，'.'表示爱丽丝可以到达这个格子，‘#’表示爱丽丝不能到达这个格子。接下来m行，表示m个隧道。每行四个正整数x1,y1,x2,y2(1<=x1,x2,y1,y2<=15),表示隧道的入口为（x1,y1),出口为（x2,y2)。数据保证隧道入口和出口位置不会出现在‘#’上。

Output

对于每个测试用例，你需要输出一个整数，表示爱丽丝通过所有隧道仅一次的最少时间。如果爱丽丝无法通过所有隧道，则输出-1。

Sample Input 1

5 4

....#

...#.

.....

.....

.....

2 3 1 4

1 2 3 5

2 3 3 1

5 4 2 1

Sample Output 1

Hint

对于样例，爱丽丝可以一开始降临在（2，3）并穿过第一个隧道到达（1，4），然后花费2分钟走向（1，2）并穿过第二个隧道到达（3，5），然后花费3分钟走向（5，4）并穿过第四个隧道到达（2，1），最后花费2分钟走向（2，3）并穿过第三个隧道到达（3，1）。至此通过所有隧道，并花费7分钟时间。

注意本题时间限制和空间限制

将隧道视为点，先bfs预处理出两两隧道间的距离，然后使用状压dp求出最小时间。

转移方程：dp[目标状态][目标点]=min（dp[目标状态][目标点]，dp[当前状态][当前点]+dis[当前点][目标点]）。

#include<bits/stdc++.h>

#define MAX 16

#define INF 0x3f3f3f3f

using namespace std;

char s[MAX][MAX];

int b[MAX][MAX],dis[MAX][MAX];

int dp[<<][MAX];

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

struct Node{

    int bx,by,ex,ey;

}a[MAX];

struct Node2{

    int x,y,s;

}node;

queue<Node2> q;

int bfs(Node u,Node v,int n){

    memset(b,,sizeof(b));

    while(q.size()){

        q.pop();

    }

    if(u.ex==v.bx&&u.ey==v.by) return ;

    node.x=u.ex;

    node.y=u.ey;

    node.s=;

    q.push(node);

    b[node.x][node.y]=;

    while(q.size()){

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

            Node2 now=q.front();

            int tx=now.x+t[i][];

            int ty=now.y+t[i][];

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

            if(s[tx][ty]=='#'||b[tx][ty]==) continue;

            b[tx][ty]=;

            if(tx==v.bx&&ty==v.by){

                return now.s+;

            }

            node.x=tx;

            node.y=ty;

            node.s=now.s+;

            q.push(node);

        }

        q.pop();

    }

    return INF;

}

int main()

{

    int n,m,i,j,k;

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

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

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

        }

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

            scanf("%d%d%d%d",&a[i].bx,&a[i].by,&a[i].ex,&a[i].ey);

        }

        memset(dis,INF,sizeof(dis));

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

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

                if(i==j) continue;

                dis[i][j]=bfs(a[i],a[j],n);

            }

        }

        memset(dp,INF,sizeof(dp));

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

            dp[<<(i-)][i]=;

        }

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

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

                if(!(i&(<<(j-)))) continue;

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

                    if(j==k||dis[j][k]==INF||!(i&(<<(k-)))) continue;

                    dp[i][k]=min(dp[i][k],dp[i^(<<(k-))][j]+dis[j][k]);

                }

            }

        }

        int ans=INF;

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

            ans=min(ans,dp[(<<m)-][i]);

        }

        if(ans==INF) printf("-1\n");

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

    }

    return ;

}

巴特西

QDUOJ 来自xjy的签到题（bfs+状压dp）

最新文章

热门文章