USACO2013 island travels

本文主要是介绍USACO2013 island travels，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：一个R行C列的矩阵，'X'表示地，'S'表示浅水，'.'表示不能走的深水。连通的X视为一个岛（不超过15个）。现在要走完所有岛，求最少的踩在浅水格子的次数。

题解：岛屿不超过15个，明显的暗示可以用状态压缩DP跑旅行商问题。但是这题需要较多的预处理。首先给每个X连通块标上岛屿的序号，然后对每一个岛屿，将它直接相邻的浅水格子压入队列跑BFS即可求出所有岛屿到他的距离。然后记得一定要跑一次Floyd！！DP的状态定义为f[s, i]表示经过了的岛屿的集合为s，最后到达i的最少路径长。

考试的时候犯了很SB的两个错误，说明写代码的时候思路不清晰。以后最好写一个函数就检查一个。

#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[

这篇关于USACO2013 island travels的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---