[USACO13JAN]岛游记Island Travels

洛咕

题意:给你一张\(r*c\)的地图，有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的.我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行.但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边.Q：你最少要经过几个浅水区？保证有解.\(r,c<=50\),联通块\(<=15.\)

分析:这道题的思路很好想,就是毒瘤.集合了\(dfs\)求联通块,\(bfs\)求最短路,状压\(dp\)多种算法.我在每个算法上都挂了半个小时......(谁能想到我现在用\(dfs\),\(bfs\)都各种问题呢\(???\))

联通块个数\(<=15\)???状压\(!!!\)设\(f[i][j]\)表示当前走到了第i个联通块,走过的联通块的集合为\(j\)时经过的最少的浅水区.

\(f[i][j]=min(f[i][j],f[k][j\)^\((1<<(i-1))])+dis[i][k]\),其中\(dis[i][k]\)表示第i个联通块和第\(k\)个联通块之间的最短距离.

所以我们只要\(dfs\)预处理出所有的联通块,然后求任意两个联通块之间的最短路,然后就可以\(DP\)了.

这题最简单的一个部分竟然是\(DP???\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=55;
int n,m,num,ans=1e9,f[20][100005];
int a[N][N],bel[N][N],visit[N][N],dis[20][20];
int dx[4]={0,0,1,-1},
    dy[4]={1,-1,0,0};
vector<pair<int,int> >g[20];
inline void dfs(int x,int y){
    bel[x][y]=num;g[num].push_back(pair<int,int>(x,y));
    for(int i=0;i<4;++i){
        int xx=x+dx[i],yy=y+dy[i];
        if(a[xx][yy]!=2||bel[xx][yy])continue;
        dfs(xx,yy);
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            char ch;cin>>ch;
            if(ch=='X')a[i][j]=2;
            if(ch=='S')a[i][j]=1;
        }
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(a[i][j]==2&&!bel[i][j])++num,dfs(i,j);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=num;++i)dis[i][i]=0;
    for(int i=1;i<=num;++i){
        memset(visit,0x3f,sizeof(visit));
        queue<pair<int,int> >q;
        for(int j=0;j<(int)g[i].size();++j)q.push(g[i][j]),visit[g[i][j].first][g[i][j].second]=0;
        while(q.size()){
            int x=q.front().first,y=q.front().second;q.pop();
            for(int j=0;j<4;++j){
                int xx=x+dx[j],yy=y+dy[j];
                if(!a[xx][yy]||bel[xx][yy]==i)continue;
                if(a[xx][yy]==2){
                    dis[i][bel[xx][yy]]=min(dis[i][bel[xx][yy]],visit[x][y]);
                    if(visit[xx][yy]>visit[x][y]){
                        visit[xx][yy]=visit[x][y];
                        q.push(pair<int,int>(xx,yy));
                    }
                }
                if(a[xx][yy]==1){
                    if(visit[xx][yy]>visit[x][y]+1){
                        visit[xx][yy]=visit[x][y]+1;
                        q.push(pair<int,int>(xx,yy));
                    }
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=num;++i)f[i][1<<(i-1)]=0;
    for(int j=1;j<(1<<num);++j){
        for(int i=1;i<=num;++i){
            if(!(j&(1<<(i-1))))continue;
            for(int k=1;k<=num;++k){
                if(!(j&(1<<(k-1))))continue;
                if(i==k)continue;
                f[i][j]=min(f[i][j],f[k][j^(1<<(i-1))]+dis[k][i]);
            }
        }
    }
    for(int i=1;i<=num;++i)ans=min(ans,f[i][(1<<num)-1]);
    printf("%d\n",ans);
    return 0;
}

[USACO13JAN]岛游记Island Travels

原文：https://www.cnblogs.com/PPXppx/p/11729413.html