算法竞赛入门经典—习题与解答.doc

第3章 比赛真题分类选解

3.1 搜 索 泡泡龙（Puzzle Dragons, ACM/ICPC Asia-Xian 2014, LA7036，难度 在泡泡龙游戏中，有一个5*6的方阵，每个格子包含一个珠子。珠子有6种类型：F、W、P、L、D和C。 游戏开始时，玩家可以选择一个珠子并且沿着一个路径移动。路径上的第一个珠子会移动到第二个的位置上，第二个会移到第三个，以此类推。最后一个珠子会移动到第一个的位置上。珠子只能沿上下左右4个方向移动。例如，如果某一行原来是“FWPLDC”，第一个珠子拿起来一直移到最右边之后，这一行就变成“WPLDCF”。 在选定路径并移动珠子之后，就开始消除。如果同一行/列有3个或以上的同样的珠子连起来（称为链），就会消除。并且在这个链上方的珠子就会落下来，消除之后不会再出现新的珠子。 如果在移动之后有多个链可被消除，它们就形成“组合（Combo）”。注意，两个同样珠子组成的链相邻或者连起来，就会被统计成一个组合，图3.1就是两个例子。 图3.1 给出方阵上每个格子放的珠子类型，需要选择一条长度不长于9的路径，使得组合的数量最多。如果有多个，就选择能够消除最多珠子的路径。如果依然有多个，选择任意一个路径长度最短的即可。输出这个路径能够消除的组合数量以及路径的长度，最后输出路径上第一个珠子的坐标（方阵左上角坐标是(1,1)，右下角是(5,6)），以及这个珠子每一步移动的方向（用‘UDLR’4个字符之一表示，分别是上下左右）。 【分析】 是遍历所有的路径起点，起点确定后对每一步的方向进行。一步就对形成路径进行消除消除后的结果更新答案。注意步数不能超过9。 消除过程 （1）Grid复制一份。 2）在副本中查找并标记所有连续3个在同一行/列的同色珠子，这些珠子都是待消除区域。 （3）标记完成就DFS消除每个区域，所有的区域进行计数。 4）将珠子消除后形成的空格上方形成的珠子往下平移。 （5）只要combo存在，消除，所有的combo完毕为止。 using namespace std; struct Point { int x, y; Point(int x=0, int y=0):x(x),y(y) {} Point operator=(const Point p){ x = p.x; y = p.y; return *this; } typedef Point Vector; Vector operator+ (const Vector A, const Vector B) { return Vector(A.x+B.x, A.y+B.y); } struct Path { int combo, drop, length; Point start; char solution[16]; void init(int len = 0, const char* str = nullptr){ start.x = 0, start.y = 0, combo = 0, drop = 0, length = len; if(str) memcpy(solution, str, len); solution[len] = 0; bool operator(const Path p) const { if(combo != bo) return combo bo; if(drop != p.drop) return drop p.drop; return length p.length; const int N = 5, M = 6; const vectorVector DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}}; const char op[5] = RLDU; char Buf[N][M+1], Grid[N][M+1], sol[11]; bool ELIM[N][M]; Path ans; bool valid(const Point p){ return p.x = 0 p.x N p.y = 0 p.y M; } //dfs消除点p周围所有颜色为c的格子，返回被消除的数量 int eliminate(const Point p, char c){ if(!valid(p)) return 0; if(Buf[p.x][p.y] != c || !ELIM[p.x][p.y]) return 0; Buf[p.x][p.y] = , ELIM[p.x][p.y] = false;