P3070 [USACO13JAN]岛游记Island Travels

毒瘤题,,, 看到$N <= 15$可以很明显发现是状压. 但是又发现给定的图不能直接用, 还得搞完联通块以后最短路预处理. 思路清晰, 代码复杂.

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int MAXN = 50 + 1;
const int INF = 0x3f3f3f3f;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int R, C;
char mp[MAXN][MAXN];

struct edge
{
    int to, cost;
};vector<edge> g[MAXN * MAXN];
vector<int> land;

inline int getnum(int x, int y){return (x - 1) * C + y;}
inline bool out(int x, int y)
{return !(1 <= x && x <= R && 1 <= y && y <= C);}

bool vis[MAXN][MAXN];

void dfs(int x, int y){
    if(vis[x][y] || mp[x][y] != 'X') return;
    vis[x][y] = true;

    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(!out(nx, ny)) dfs(nx, ny);
    }
    return ;
}

void init(){
    for(int i = 1; i <= R; i++)
        for(int j = 1; j <= C; j++) if(mp[i][j] == 'X' && !vis[i][j])
            land.push_back(getnum(i, j)), dfs(i, j);
}

int dis[MAXN * MAXN], d[16][16];

inline bool tension(const int &st, int &lg){
    return st < lg ? (lg = st, true) : false;
}

void dijkstra(int S, int idx){
    deque<int> q;
    memset(dis, 0x3f, sizeof(dis));

    dis[S] = 0, q.push_back(S);
    while(!q.empty()){
        int u = q.front(); q.pop_front();
        for(int i = 0; i < (int) g[u].size(); i++){
            edge &e = g[u][i];
            if(tension(dis[u] + e.cost, dis[e.to])){
                if(e.cost) q.push_back(e.to);
                else q.push_front(e.to);
            }
        }
    }

    for(int i = 0; i < (int) land.size(); i++)
        d[idx][i] = dis[land[i]];
}

int N;
int f[(1 << 16)][16];

int main()
{
//  freopen("p3070.in", "r", stdin);
    cin>>R>>C;
    for(int i = 1; i <= R; i++){
        scanf(" ");
        for(int j = 1; j <= C; j++) mp[i][j] = getchar();
    }
    
    for(int i = 1; i <= R; i++)
        for(int j = 1; j <= C; j++) if(mp[i][j] != '.')
            for(int k = 0; k < 4; k++){
                int nx = i + dx[k], ny = j + dy[k];
                if(!out(nx, ny) && mp[nx][ny] != '.'){
                    if(mp[nx][ny] == 'S') g[getnum(i, j)].push_back((edge){getnum(nx, ny), 1});
                    if(mp[nx][ny] == 'X') g[getnum(i, j)].push_back((edge){getnum(nx, ny), 0});
                }
            }

    init(); memset(d, 0x3f, sizeof(d));
    for(int i = 0; i < (int) land.size(); i++)
        dijkstra(land[i], i);
    
    N = land.size(); memset(f, 0x3f, sizeof(f));

    for(int i = 0; i < N; i++) f[(1 << i)][i] = 0;
    for(int i = 0; i < (1 << N); i++)
        for(int j = 0; j < N; j++) if(i & (1 << j)){
            for(int k = 0; k < N; k++) 
                f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + d[j][k]);
        }
    int ans = (1 << 30);
    for(int i = 0; i < N; i++) ans = min(ans, f[(1 << N) - 1][i]);
    cout<<ans<<endl;
    return 0;
}