Baudelaire is Programmer

种子染色法

种子染色法英文叫做Flood Fill ，实际上Flood Fill这个名称更贴切一点，因为这个方法作用在一个图的结点上时恰似洪水一样“淹没”与之相连的其他结点并以相同的方式蔓延出去，这个方法通常用于计算一个图的极大连通子图（这里的“图”是图论的概念）。设想一个无向图，我们从这个图中一个未标号（“标号”可以理解为“染色”）的结点开始，将此结点和从这个结点出发可达的所有结点都赋予相同的标号（染上相同的颜色），那么我们就得到了这些被标号的结点所组成的一个极大连通子图，搜索下一个未标号的结点并重复上述过程我们便可以找到所有的极大连通子图。“染色”的过程可以用DFS或者BFS实现，如果结点数为V，边数为E，因为我们在Flood Fill过程中“造访”每个结点两次，“造访”每条边两次，所以得到所有极大连通子图的时间复杂度为o(V+E) 。

来自Wikipedia的一个示例：

想象每个白色方块为图中的结点，相邻的方块（上下左右）有边相连，那么这个图就有三个极大连通子图，这演示了Flood Fill查找其中一个极大连通子图的过程。

应用

给定一个城堡的平面图，例如：

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#   
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #   
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #   
   ############################# 

#  = Wall     -,|  = No wall
-> = Points to the wall to remove to
     make the largest possible new room

要求求出房间数和最大的房间的面积，另外找到一堵墙，我们将其拆掉之后可以得到一个尽可能大的新房间，平面图的表示以及输出遵循以下规则：

INPUT FORMAT

The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above.

Each module number tells how many of the four walls exist and is the sum of up to four integers:

• 1: wall to the west
• 2: wall to the north
• 4: wall to the east
• 8: wall to the south

Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1.

SAMPLE INPUT (file castle.in)

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

OUTPUT FORMAT

The output contains several lines:

Choose the optimal wall to remove from the set of optimal walls by choosing the module farthest to the west (and then, if still tied, farthest to the south). If still tied, choose 'N' before 'E'. Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.

5
9
16
4 1 E

平面图的块数最多为50*50=2500，墙数最多为49*50*2=4900，枚举要拆掉的墙，并应用 Flood Fill 填充整个图我们可以求得每种情况下最大的房间面积，应用DFS进行搜索，使用位运算检测相应的比特位以确定四周有没有墙壁，同样使用位运算可以模拟拆墙（注意要同时对相邻两个块进行操作以拆掉一面墙）和补墙。计算量最多为4900*(2*2500+2*4900)=72520000 不会超时。因为我们要保留最优解中最靠西边和南边的墙，所以要自东向西，自北向南进行枚举，因为要优先使用北面的墙，我们按“东”、“北”的顺序枚举每个块对应的两面墙。

查看我的程序源码：

/*
ID: *******
LANG: C++
TASK: castle
*/
#include<stdio.h>
#include<stdlib.h>

int row,col;
int map[50][50];
FILE *fin,*fout;
int num;//房间数
int max;//最大房间面积
int count;//房间面积
bool filled[50][50];
int direct[4][2]={
	{0,-1},{-1,0},{0,1},{1,0}
};

void dfs(int i,int j){
	if(i<0||i>=row||j<0||j>=col)return;
	if(filled[i][j])return;
	count++;
	filled[i][j]=true;
	int a=1,p;
	for(p=0;p<=3;p++){
		if(((a<<p)&map[i][j])==0)
			dfs(i+direct[p][0],j+direct[p][1]);
	}
}

void floodfill(){
	int i,j;
	max=0;
	num=0;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
			filled[i][j]=false;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
			if(!filled[i][j]){//寻找未标号的块
				count=0;
				dfs(i,j);
				num++;
				if(max<count)
					max=count;
			}
}

int main(){
	fin=fopen("castle.in","r");
	fout=fopen("castle.out","w");
	fscanf(fin,"%d %d",&col,&row);
	int i,j;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
			fscanf(fin,"%d",&map[i][j]);
	floodfill();
	fprintf(fout,"%d\n%d\n",num,max);
	int verymax=0;
	int mi,mj;
	char w;
	for(j=col-1;j>=0;j--)
		for(i=0;i<row;i++){
			int a=4,p;
			for(p=1;p<=2;p++){
				a/=p;
				int b=a==2?8:1;
				if(!(map[i][j]&a))continue;//判断有没有墙
				map[i][j]&=~a;//拆墙
				if(a==2&&i-1>=0)map[i-1][j]&=~b;
				if(a==4&&j+1<col)map[i][j+1]&=~b;//拆掉相邻块对应的墙
				floodfill();
				if(verymax<=max){
					verymax=max;
					mi=i;
					mj=j;
					w=a==2?'N':'E';
				}
				map[i][j]|=a;
				if(a==2&&i-1>=0)map[i-1][j]|=b;
				if(a==4&&j+1<col)map[i][j+1]|=b;//补墙以继续枚举
			}
		}
	fprintf(fout,"%d\n%d %d %c\n",verymax,mi+1,mj+1,w);
	return 0;
}