Sicily题解 广度优先搜索的简单应用

对算法感兴趣的都可以进来看看哦...



先仔细阅读题目

Sicily 13061: Block Party

Description

There are a variety of games such as Bejeweled and Shape Shift that are played on a grid of tiles, each having a color and sometimes another image. A move is a swap of two tiles that have the same shape on them. When a swap results in a chain 4 or more of the same color, then those tiles are removed from the board and the tiles above them slide down to fill the gaps. (Two tiles are in a chain if they share a side.) After tiles have slid down, more chains might form. Note: No tiles slide until all chains in the current configuration of the board have been removed.

A board can be represented by a rectangular arrangement of letters. One such arrangement is shown in the figure below. On that board, there are two chains of length 4, one of the character "R" and one of the character "B". Note that to be a chain, the characters must be an exact match; case is significant. The start of a sequence of reactions is shown in the figure. Reactions continue until there are no more chains. In real games, new tiles replace open spaces in the grid, but we will not be concerned with replacement tiles.

Write a program that processes the sequence of chain reactions in a board.


Input

The input is a sequence of test cases, each representing a board. The first line of each test case contains two nonnegative integer values w (0 < w < 256) and h (0 < h < 256) separated by a space giving the width and height of the board (in tiles). The line containing the dimensions is followed by h lines of w non-blank characters each. The end of input is indicated by a line containing 0 0 for w and h. This case should not be processed.

Output

The output for each test case is the number of the test case (where the first test case is numbered 1) followed by a colon and a space followed by an integer value that shows the number of tiles remaining after all reactions complete.

Sample Input

7 9
YOOGYBY
GRGYBbB
OGRGOBY
BBGBRRB
YRYRROR
BOYBOBO
YGBYBBG
OOBYBRG
BBYRRBO
3 2
YBY
BYB
0 0Sample Output1: 51
2: 6题解

我简单翻译一下好了, 这个类似于消消乐, 就像上面提供的图片一样, 从初始化的二维字母集合开始, 如果在这个二维字母集合中存在一个位置A, 使得从A出发可以找到与这个位置的字母相同的所有位置adj(A), 并且length(adj(A)) + 1 >= 4, 那么这些位置的字母就可以chain起来, 然后slide掉, slide掉的效果是相同字母的chain删除掉, 并且周围的字母都会受影响(自由坠落), 之后如果还能够chain则重复上述流程.

看到这道题的数据量并不大, 所以实际上最最暴力的思路, 也是最简单的思路:

1. 从初始二维字母集合开始, 对每一个位置进行遍历, 查看这个位置是否满足chain条件(这里需要使用广度优先搜索来进行判断), 如果满足, 就标记它和周围的字母为删除状态

2. 每次遍历完之后, 就根据刚刚标记的删除状态进行对应的slide操作, 之后得到一个新的二维字母集合, 再重复chain和slide操作, 直到无法chain为止, 算法结束, 得到最后的二维字母集合即可.

关于广度优先搜索的实现, 这里就使用下图进行介绍, 不再具体描述.





那么首先我们需要描述二维字母集合中的每一个位置, 如下所示, x和y表示为坐标, value表示字母的值.



其次我们要思考需要用到的数据结构:

1. 输入数据: row行column列的二维字母集合board[MAX_N][MAX_N], 其中MAX_N = 256;
2. 输出数据的样例标识, 表示当前输出是第几个输出: cases
3. 对于每一次二维字母集合的遍历, 都需要标识哪些字母被slide掉了, 从而才能进行slide操作, 我们这里使用二维布尔数组来表示: isRemoved[MAX_N][MAX_N];
4. 由题意可以知道, slide操作需要逐列扫描, 将标记为removed的位置进行字母自由坠落的调整, 也就是要对isRemoved[MAX_N]数组进行转换, 这里需要使用辅助堆栈ha来完成操作;
5. 要判断每个位置是否可构成chain, 需要对每个位置进行广搜操作, 而每个位置的广搜方向只有上下左右, 于是需要dx和dy两个一维四列数组来表示位置的可选方向, 需要节点pivot和temp以及队列q和closed来辅助广度优先搜索的操作(closed的作用是将给定位置的所有满足chain条件的节点保存起来), 需要isVisited[MAX_N][MAX_N]布尔数组来标识哪些位置已经进行访问了(以免重复搜索),
6. 如何让chain和slide操作能够持续不断地进行呢需要布尔标识can, 每次循环前置位为false, 如果有可以进行chain操作的位置, 就将can置位true, 否则表示算法已经结束, 应该退出循环.

综上所述, 我们的全局变量设计如下:



输入和初始化

针对题目的输入输出要求, 在每一次测试用例经过时都要对相应数据进行初始化, 这里需要注意一个坑: cin.get(); 因为当你输入列和行的时候会按下回车, 如果没有cin.get()的话你的这个回车会被board给吸收了. 其中isRemoved也要全部初始化为false



chain和slide操作的循环初始化


每一次can循环都是一次chain和slide的过程:

chain

chain的实现方式很简单: 对于每一个位置, 先判断这个位置(i, j)是不是被removed了, 如果是, 那么就对这个位置进行广度优先搜索

广度优先搜索的作用就是将所有与当前位置(i, j)字母相同的位置保存到closed队列中, 如果这个队列的大小大于等于4, 就达到了chain条件, 相应的位置就要被isRemoved



slide

slide操作其实也很简单, 只不过需要注意的是需要逐列扫描, 在对列进行扫描的过程中, 先把没有被slide的位置给存储在堆栈中, 然后从最底行开始将堆栈中的值一个接着一个地pop到对应的位置, 那么最上面的位置自然就需要被removed了, 这就是slide操作


输出

将完成can循环后的isRemoved数组做一个统计即可.



从ac结果看这样子的算法是可行的, 虽然运行内存看起来好像有点多, 但是思路基本如上

    关注 黄勇进