首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
usaco2013专题
USACO2013 island travels
题意:一个R行C列的矩阵,'X'表示地,'S'表示浅水,'.'表示不能走的深水。连通的X视为一个岛(不超过15个)。现在要走完所有岛,求最少的踩在浅水格子的次数。 题解:岛屿不超过15个,明显的暗示可以用状态压缩DP跑旅行商问题。但是这题需要较多的预处理。首先给每个X连通块标上岛屿的序号,然后对每一个岛屿,将它直接相邻的浅水格子压入队列跑BFS即可求出所有岛屿到他的距离。然后记得一定要跑一次Fl
阅读更多...