USACO2013 island travels

題意:R行C列の行列,'X'は地を表し,'S'は浅水を表し,'.'歩けない深水を表す.連通するXは1つの島(15を超えない)と見なされる.今すべての島を歩き終えて、最も少ない浅い水の格子を踏む回数を求めます.
标题:島は15個を超えず、明らかな暗示は状態圧縮DPで旅行業者問題を走ることができる.しかし、この問題はより多くの前処理が必要だ.まず、各X連通ブロックに島の番号を付け、その後、各島に対して、直接隣接する浅い格子を列に押し込んでBFSを走ると、すべての島から彼までの距離を求めることができる.そしてぜひ一度はFloydを走ってみてください!!DPの状態はf[s,i]と定義され,通過した島の集合がsであり,最後にiに到達する最小経路長を表す.
試験の時にとてもSBの2つの間違いを犯して、コードを書く時構想がはっきりしていないことを説明します.後で関数を1つ書いてチェックしたほうがいいです.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define Min(a,b) ((a)<(b)?(a):(b))
#define inmap(x,y) (x>0 && y>0 && x<=R && y<=C)
const int MAXN = 105;
const int dd[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int N, R, C;
int dis[20][20];
char sea[MAXN][MAXN];
int cnt;
const int INF = 0x3f3f3f3f;

#define code(x,y) ((x-1)*C+y)
#define getx(s) ((s-1)/C+1)
#define gety(s) ((s-1)%C+1)
void mark(int x, int y)
{
	queue<int> Q;
	Q.push(code(x,y));
	++cnt;
	while (!Q.empty()) {
		x = getx(Q.front());
		y = gety(Q.front());
		sea[x][y] = cnt;
		Q.pop();
		for (int i = 0; i<4; ++i) {
			int tx = x+dd[i][0], ty = y+dd[i][1];
			if (inmap(tx,ty) && sea[tx][ty]=='X')
				Q.push(code(tx, ty));
		}
	}
}

int step[MAXN][MAXN];
void BFS(int id)
{
    int i, j, k, x, y, tx, ty;
    queue<int> Q;
    memset(step, 0, sizeof step);
    for (i = 1; i<=R; ++i)
		for (j = 1; j<=C; ++j)
			if (sea[i][j] == id)
				for (k = 0; k<4; ++k) {
					tx = i+dd[k][0], ty = j+dd[k][1];
					if (inmap(tx,ty) && sea[tx][ty]=='S')//                      ！！
						Q.push(code(tx, ty)), step[tx][ty] = 1;
				}
    while (!Q.empty()) {
		x = getx(Q.front()), y = gety(Q.front());
		Q.pop();
		for (i = 0; i<4; ++i) {
			tx = x+dd[i][0], ty = y+dd[i][1];
			if (!inmap(tx,ty)) continue;
			if (sea[tx][ty]=='S' && !step[tx][ty])
				Q.push(code(tx,ty)), step[tx][ty] = step[x][y]+1;
			else if (1<=sea[tx][ty] && sea[tx][ty]<=cnt && sea[tx][ty]!=id) {
				j = sea[tx][ty];
				dis[id][j] = Min(dis[id][j], step[x][y]),
				dis[j][id] = dis[id][j];
			}
		}
	}
}
  
void Floyd()//        floyd ，           。
{
	for (int k = 1; k<=cnt; ++k)
		for (int i = 1; i<=cnt; ++i)
			for (int j = 1; j<=cnt; ++j)
				dis[i][j] = Min(dis[i][j], dis[i][k] + dis[k][j]);
}
  
int f[(1<<16)+1][16]; 
int ans = INF; 
void DoDP() 
{ 
    memset(f, 0x3f, sizeof f);
    int s, s1, i, j;
    for (i = 1; i<=cnt; ++i)
		f[1<<(i-1)][i] = 0;
    for (s = 1; s < (1<<cnt); ++s)
		for (i = 1; i<=cnt; ++i)
		{
			if (!(s&(1<<(i-1)))) continue;
			s1 = s ^ (1<<(i-1));
			for (j = 1; j<=cnt; ++j)
			{
				if (!(s1&(1<<(j-1)))) continue;
				f[s][i] = Min(f[s][i], f[s1][j]+dis[j][i]);
			}
		}
	for (i = 1; i<=cnt; ++i)
		ans = Min(ans, f[(1<<cnt)-1][i]);
}

int main() 
{ 
    int i, j; 
    scanf("%d%d", &R, &C); 
    memset(dis, 0x3f, sizeof dis); 
    for (i = 1; i<=R; ++i) 
        scanf("%s", sea[i]+1); 
    for (i = 1; i<=R; ++i) 
        for (j = 1; j<=C; ++j) 
            if (sea[i][j] == 'X') 
                mark(i, j); 
    for (i = 1; i<=cnt; ++i) 
    BFS(i); 
    Floyd();
    DoDP();
    printf("%d
", ans);
    return 0;
}