Connect(bzoj 1948)

Description

给定一个R*C大小的迷宫，其中R,C均为奇数迷宫中坐标为两个奇数的点不能通过，称为障碍，迷宫中其他不能通过的点统称为墙壁坐标为两个偶数的点可以通过，称为房间，迷宫中其他可通过的点称为走廊。迷宫有边界迷宫中放置有若干个物品(偶数个)，物品一定放置在房间中问如何将这些物品配对可以使得所有物品对之间路径的总和最小，任两条路径不能相交，并求路径

Input

第一行输入为两个整数： R与C(5 ≤ R ≤ 25，5 ≤ C ≤ 80) 其中R为行数，C为列数，R，C均为奇数。接下来的R行每行包括C个字符，每个字符都是’+’、’|’、’-‘、空格或’X’中的一个，分别表示障碍及两种墙壁、空格表示房间或可通过的走廊，X表示房间中的物品。

Output

输出的第一行是一个整数，即最小分值。

/*

    插头DP

    这道题看了一晚上了，还是有很多地方不理解，Orz~

*/

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int n,m,inf,cnt;

int f[][][(<<)+],blo[][][];

char s1[][],s[][];

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

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

void upd(int &x,int y){x=min(x,y);}

int trs(int x,int y){

    x=(x>>)<<;x|=y&;

    x|=((y&)>>)<<m;

    return x;

}

int main(){

    scanf("%d%d",&n,&m);gets(s1[]+);

    for(int i=;i<=n;i++) gets(s1[i]+);

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

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

            s[j][i]=s1[i][j],cnt+=(s1[i][j]=='X');

    swap(n,m);

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

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

            for(int k=;k<;k++)

                blo[i>>][j>>][k]=(s[i+dy[k]][j+dx[k]]!=' ');

    n/=;m/=;

    memset(f[],0x3f,sizeof(f[]));

    inf=f[][][];f[][][]=;

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

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

            if(j==m)

                memset(f[~i&],0x3f,sizeof(f[~i&]));

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

                if(f[i&][j][k]==inf) continue;

                int *nex;

                if(j==m) nex=f[~i&][];

                else nex=f[i&][j+];

                int v1=blo[i][j][],v2=blo[i][j][],val=f[i&][j][k];

                if(s[i<<][j<<]=='X'){

                    if((k&)==) continue;

                    if((k&)==){

                        if(!v2) upd(nex[trs(k,)],val+);

                        if(!v1) upd(nex[trs(k,)],val+);

                    }

                    else upd(nex[trs(k,)],val);

                }

                else{

                    if((k&)==) upd(nex[trs(k,)],val+);

                    else if((k&)==){

                        upd(nex[trs(k,)],val);

                        if(!v1&&!v2) upd(nex[trs(k,)],val+);

                    }

                    else {

                        if(!v2) upd(nex[trs(k,)],val+);

                        if(!v1) upd(nex[trs(k,)],val+);

                    }

                }

            }

        }

    printf("%d\n",f[(n+)&][][]+cnt/);

    return ;

}

巴特西

Connect(bzoj 1948)

Description

Input

Output

最新文章

热门文章