The Castle - USACO 2.1.1

thecastle - codetrick

In a stroke of luck almost beyond imagination, Farmer John was sent a ticket to the Irish Sweepstakes (really a lottery) for his birthday. This ticket turned out to have only the winning number for the lottery! Farmer John won a fabulous castle in the Irish countryside.

Bragging rights being what they are in Wisconsin, Farmer John wished to tell his cows all about the castle. He wanted to know how many rooms it has and how big the largest room was. In fact, he wants to take out a single wall to make an even bigger room.

Your task is to help Farmer John know the exact room count and sizes.

The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their "outer edges" to keep out the wind and rain.

Consider this annotated floorplan of a castle:

     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

By way of example, this castle sits on a 7 x 4 base. A "room" includes any set of connected "squares" in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).

Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.

The castle always has at least two rooms and always has a wall that can be removed.

PROGRAM NAME: castle

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.

Line 1:	Two space-separated integers: M and N
Line 2..:	M x N integers, several per line.

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:

Line 1:	The number of rooms the castle has.
Line 2:	The size of the largest room
Line 3:	The size of the largest room creatable by removing one wall
Line 4:	The single wall to remove to make the largest room possible

Choose the optimal wall to remove from the set of optimal walls by choosing the wall farthest to the west (and then, if still tied, farthest to the south). 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.

SAMPLE OUTPUT (file castle.out)

5
9
16
4 1 E

http://www.boyu0.com/usaco-the-castle/
计算每个房间的大小肯定用flood fill算法啦，然后再flood fill的同时记录下相邻房间的序号跟可以选择推倒的最优墙壁号跟方向，最后遍历每个neighbor，算出是哪两个房间推倒墙后可获得最大的值就可以啦.
http://enumz.github.io/2015/05/26/USACO-Section-2-1/
先用DFS将房间个数ans1和最大房间大小ans2搜索出来。（可以把不同的房间染上不同的颜色）
再从左下角遍历一边房间，若遇到一堵墙两边的颜色不同且两个颜色的房间面积之和大于(严格大于)ans3，则更新ans3和ans4

顺便说说那个翻译。对于拆除的墙壁，应当尽量靠西，其次在考虑南北。对于同一格中的墙壁，如果拆除后得到的房间数同样多，应当优先拆除北面的墙壁（只有两种选择，一种北面，一中东面）。

再说算法，第一问用FLOOD FILL，用一个判重数组，判断房间是否已被访问过，然后就是向四周扩展。我用了位运算来判断方向的可行性。拿13来说，如果13 and 1=0，那么他的西面就没有墙，其他类似。把同一个房间的格子赋予一个相同的编号，为第二问做准备。

对于第二问，从左下到右上扫面一遍，如果他的邻格与他的编号不同，且他们加起来的面积为当前最大，则记录下来，于是问题顺利解决。

X. BFS
http://blog.csdn.net/dunceiam/article/details/43968115

        先遍历所有房间，找出连起来的块标记好，到这里为止，算出了房间数和最大房间。再遍历一遍房间+标记，由于题目条件，所以只用敲掉北墙和东墙，从而求出敲掉一面墙后的最大值。

        数组的边界上我做了一个小trick，对于四周的边界多加了一行。这样在边界判断左右上下元素的时候，都不会越界。

        也算是给跟我一样讨厌数组越界的人提供个思路。

        对于房间遍历的部分，我用了BFS的迭代，对于每个被检查的房间，都检查它的四周，有没有与它相连的部分，有的话就迭代。

        在第一次遍历后，记录下来的是每一个房间所在块的大小、对每一个房间都做了代表块的标号。

http://qingtangpaomian.iteye.com/blog/1635203

这里要特别注意枚举的顺序，题目有如下说明“有多解时选（重心）最靠西的（仍然有多解时选这些里面（重心）最靠南的）”，所以最后的枚举我们要按照从西向东，从南到北的顺序。

1.   
2. public class castle {  
3.     static int[][] colors;  
4.     static int[][] walls;  
5.     static int colNum;  
6.     static int rowNum;  
7.     static HashMap<Integer,Integer> counts;  
8.     static int max;  
9.     static int maxJoin;  
10.     static String maxWall;  
11.       
12.     public static void main(String[] args) {  
13.         try {    
14.             Scanner in = new Scanner(new BufferedReader(new FileReader(  
15.             "castle.in")));  
16.             PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(  
17.             "castle.out")));  
18.               
19.              colNum = in.nextInt();  
20.              rowNum = in.nextInt();  
21.               
22.             colors = new int[rowNum+2][colNum+2];  
23.             walls = new int[rowNum+2][colNum+2];  
24.             counts = new HashMap<Integer, Integer>();  
25.             counts.put(0, 0);  
26.             max = 0;  
27.             int color = 1;  
28.               
29.             for (int i=1;i<=rowNum;i++){  
30.                 for (int j=1;j<=colNum;j++){  
31.                     walls[i][j] = in.nextInt();  
32.                 }  
33.             }  
34.               
35.             for (int i=1;i<=rowNum;i++){  
36.                 for (int j=1;j<=colNum;j++){  
37.                     if (colors[i][j]==0){  
38.                         LinkedList<Node> ll = new LinkedList<Node>();  
39.                         ll.add(new Node(i,j));  
40.                         colors[i][j] = color;  
41.                         bfs(ll,color);   
42.                         color ++ ;  
43.                     }  
44.                 }  
45.             }  
46.             pw.println(color-1);  
47.             pw.println(max);  
48.               
49.             maxJoin = max;  
50.             for (int j=1;j<=colNum;j++){  
51.                 for (int i=rowNum;i>=1;i--){  
52.                     if(colors[i][j]!=colors[i][j-1]){  
53.                         if (counts.get(colors[i][j])+counts.get(colors[i][j-1])>maxJoin){  
54.                             maxJoin = counts.get(colors[i][j])+counts.get(colors[i][j-1]);  
55.                             maxWall = i+" "+j+"W";  
56.                         }  
57.                     }  
58.                       
59.                     if(colors[i][j]!=colors[i+1][j]){  
60.                         if (counts.get(colors[i][j])+counts.get(colors[i+1][j])>maxJoin){  
61.                             maxJoin = counts.get(colors[i][j])+counts.get(colors[i+1][j]);  
62.                             maxWall = i+" "+j+" S";  
63.                         }  
64.                     }  
65.                       
66.                     if(colors[i][j]!=colors[i-1][j]){  
67.                         if (counts.get(colors[i][j])+counts.get(colors[i-1][j])>maxJoin){  
68.                             maxJoin = counts.get(colors[i][j])+counts.get(colors[i-1][j]);  
69.                             maxWall = i+" "+j+" N";  
70.                         }  
71.                     }  
72.                       
73.                     if(colors[i][j]!=colors[i][j+1]){  
74.                         if (counts.get(colors[i][j])+counts.get(colors[i][j+1])>maxJoin){  
75.                             maxJoin = counts.get(colors[i][j])+counts.get(colors[i][j+1]);  
76.                             maxWall = i+" "+j+" E";  
77.                         }  
78.                     }  
79.                 }  
80.             }  
81.             pw.println(maxJoin);  
82.             pw.println(maxWall);  
83.               
84.               
85.             pw.close();  
86.               
87.         } catch (Exception e) {  
88.             e.printStackTrace();  
89.         }  
90.     }  
91.       
92.     public static void bfs(LinkedList<Node> ll, int color){  
93.         int count = 0;  
94.         while (ll.size()!=0){  
95.             Node node = ll.removeFirst();  
96.             int wall = walls[node.x][node.y];  
97.             count ++;  
98.             if (wall>=8){  
99.                 wall = wall - 8;  
100.             } else {  
101.                 if(node.x+1<=rowNum){  
102.                     if (colors[node.x+1][node.y]==0){  
103.                         ll.add(new Node(node.x+1,node.y));  
104.                         colors[node.x+1][node.y]=color;  
105.                     }  
106.                 }  
107.             }  
108.             if (wall >=4){  
109.                 wall = wall -4;  
110.             } else {  
111.                 if(node.y+1<=colNum){  
112.                     if (colors[node.x][node.y+1]==0){  
113.                         ll.add(new Node(node.x,node.y+1));  
114.                         colors[node.x][node.y+1]=color;  
115.                     }  
116.                 }  
117.             }  
118.             if (wall >=2){  
119.                 wall = wall -2;  
120.             } else {  
121.                 if(node.x-1>=1){  
122.                     if (colors[node.x-1][node.y]==0){  
123.                         ll.add(new Node(node.x-1,node.y));  
124.                         colors[node.x-1][node.y]=color;  
125.                     }  
126.                 }  
127.             }  
128.             if (wall == 0){  
129.                 if(node.y-1>=1){  
130.                     if (colors[node.x][node.y-1]==0){  
131.                         ll.add(new Node(node.x,node.y-1));  
132.                         colors[node.x][node.y-1]=color;  
133.                     }  
134.                 }  
135.             }  
136.         }  
137.         counts.put(color, count);  
138.         if (count > max){  
139.             max = count;  
140.         }  
141.     }  
142. }  
143.   
144. class Node{  
145.     int x ;  
146.     int y ;  
147.     public Node(int x, int y) {  
148.         this.x = x;  
149.         this.y = y;  
150.     }  
151. } 

X. DFS
http://huobengle.iteye.com/blog/1386730
https://github.com/licong1112/usaco/blob/master/castle.java

	public void solve() throws IOException { int n = readInt(), m = readInt();
	int[][] land = new int[m][n];
	for (int i = 0; i < m; ++i) {
	for (int j = 0; j < n; ++j) {
	land[i][j] = readInt();
	}
	}
	int[] area = new int[m*n+10];
	int[][] group = new int[m][n];
	int max_area = discoverAreaAndGetMaxArea(land, group, area);
	int landmark = 1;
	while (area[landmark] > 0) {
	++landmark;
	}
	int[] max_area_coord = new int[3];
	int max_area_break_wall = discoverMaxAreaBreakWall(group, area, max_area_coord);
	out.println(landmark-1);
	out.println(max_area);
	out.println(max_area_break_wall);
	out.print(max_area_coord[0] + " " + max_area_coord[1] + " ");
	out.println(max_area_coord[2] == 1 ? "N" : "E");
	}
	public int discoverMaxAreaBreakWall(int[][] group, int[] area, int[] max_area_coord) {
	int max_area_break_wall = 0;
	int m = group.length, n = group[0].length;
	int new_area = 0;
	for (int j = 0; j < n; ++j) {
	for (int i = m-1; i >= 0; --i) {
	// North
	if (i > 0 && group[i][j] != group[i-1][j]) {
	new_area = area[group[i][j]] + area[group[i-1][j]];
	if (max_area_break_wall < new_area) {
	max_area_break_wall = new_area;
	max_area_coord[0] = i+1;
	max_area_coord[1] = j+1;
	max_area_coord[2] = 1;
	}
	}
	// East
	if (j < n-1 && group[i][j] != group[i][j+1]) {
	new_area = area[group[i][j]] + area[group[i][j+1]];
	if (max_area_break_wall < new_area) {
	max_area_break_wall = new_area;
	max_area_coord[0] = i+1;
	max_area_coord[1] = j+1;
	max_area_coord[2] = 2;
	}
	}
	}
	}
	return max_area_break_wall;
	}
	public int discoverAreaAndGetMaxArea(int[][] land, int[][] group, int[] area) {
	int m = land.length, n = land[0].length;
	int landmark = 1;
	int max_area = 0;
	for (int i = 0; i < m; ++i) {
	for (int j = 0; j < n; ++j) {
	if (group[i][j] == 0) {
	group[i][j] = landmark;
	area[landmark]++;
	dfs(land, group, area, i, j, landmark);
	max_area = Math.max(max_area, area[landmark]);
	++landmark;
	}
	}
	}
	return max_area;
	}
	public void dfs(int[][] land, int[][] group, int[] area, int row, int col, int landmark) {
	// West
	if ((land[row][col] & 1) == 0 && col > 0 && group[row][col-1] == 0) {
	group[row][col-1] = landmark;
	area[landmark]++;
	dfs(land, group, area, row, col-1, landmark);
	}
	// North
	if (((land[row][col] >> 1) & 1) == 0 && row > 0 && group[row-1][col] == 0) {
	group[row-1][col] = landmark;
	area[landmark]++;
	dfs(land, group, area, row-1, col, landmark);
	}
	// East
	if (((land[row][col] >> 2) & 1) == 0 && col < land[0].length-1 && group[row][col+1] == 0) {
	group[row][col+1] = landmark;
	area[landmark]++;
	dfs(land, group, area, row, col+1, landmark);
	}
	// South
	if (((land[row][col] >> 3) & 1) == 0 && row < land.length-1 && group[row+1][col] == 0) {
	group[row+1][col] = landmark;
	area[landmark]++;
	dfs(land, group, area, row+1, col, landmark);
	}
	}

https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection2/src/castle.java

	// dsf recursive floodfill is fine here // check every two rooms' sum of size
	// only need to break walls to the north and to the east
	public class castle {
	private static int M;
	private static int N;
	private static int[][] rooms;
	private static int[][] roomscolor;
	private static int maxcolor = 1;
	private static int[] colorcnt;
	public static void main(String[] args) throws Exception{
	BufferedReader in = new BufferedReader(new FileReader("castle.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("castle.out")),true);
	StringTokenizer st = new StringTokenizer(in.readLine());
	M = Integer.parseInt(st.nextToken());
	N = Integer.parseInt(st.nextToken());
	rooms = new int[N][M];
	roomscolor = new int[N][M];
	colorcnt = new int[M * N + 1];
	// flood fill
	for(int i = 0; i < N; i++){
	st = new StringTokenizer(in.readLine());
	for(int j = 0; j < M; j++)
	rooms[i][j] = Integer.parseInt(st.nextToken());
	}
	for(int i = 0; i < N; i++)
	for(int j = 0; j < M; j++)
	if(roomscolor[i][j] == 0)
	dfs(i,j,maxcolor++);
	out.println(maxcolor-1);
	int maxCount = 0;
	for(int i : colorcnt)
	maxCount = i > maxCount ? i : maxCount;
	out.println(maxCount);
	// break wall
	maxCount = 0;
	int wallI = 0;
	int wallJ = 0;
	char direction = 0;
	for(int j = 0; j < M; j++)
	for(int i = N-1; i >=0; i--){
	if( i-1 >=0 && roomscolor[i-1][j] != roomscolor[i][j]){
	int tmp = colorcnt[roomscolor[i-1][j]] + colorcnt[roomscolor[i][j]];
	if(maxCount < tmp){
	maxCount = tmp;
	wallJ = j;
	wallI = i;
	direction = 'N';
	}
	}
	if( j+1 <=M-1 && roomscolor[i][j+1] != roomscolor[i][j]){
	int tmp = colorcnt[roomscolor[i][j+1]] + colorcnt[roomscolor[i][j]];
	if(maxCount < tmp){
	maxCount = tmp;
	wallJ = j;
	wallI = i;
	direction = 'E';
	}
	}
	}
	out.println(maxCount);
	out.println(wallI+1 + " " + (wallJ+1) +" " + direction);
	System.exit(0);
	}
	private static void dfs(int i, int j, int color){
	if(roomscolor[i][j] != 0)
	return;
	roomscolor[i][j] = color;
	colorcnt[color]++;
	// Pay attention to the priority of operator &
	// To West
	if( (rooms[i][j] & 1) == 0 && j-1 >= 0)
	dfs(i,j-1,color);
	// To North
	if( (rooms[i][j] & 2) == 0 && i-1 >= 0)
	dfs(i-1,j,color);
	// To East
	if( (rooms[i][j] & 4) == 0 && j+1 <= M-1)
	dfs(i,j+1,color);
	// To South
	if( (rooms[i][j] & 8) == 0 && i+1 <= N-1)
	dfs(i+1,j,color);
	}

X. Union-find
http://www.dlifep.com/?p=79

题目要求输出地图中房间的数目、最大的房间大小、移掉一块墙的最大的房间大小和这块墙的位置。

我们先用构建并查集，把连通的一个一个的小格子作为并查集里面相关的元素，构建完之后，我们便得到了一片森林（并查集）。

至于房间的数目，我们只要统计并查集里面树的数量就可以了，因为这个时候连通的房间已经构成了一棵树。因为我是用数组存的并查集，为了统计树的数量，我先根据每一个节点，更新他的父亲（比如i节点，Set.get_father(i)），通过路径压缩把这个节点的最“父亲”的父亲找到。于是对于同一棵树，每个节点的父亲都是一个相同的节点。

然后我们把并查集里面的那个记父亲的节点扫一遍，看有多少个不同的父亲，就可以得出有多少个房间。

至于最大的房间的大小，我最开始想的是用类似于并查集里面的按秩合并的方法记以某个节点作为根节点的子树的节点数量（这句话考小学语文），但是写起来怕出错，鉴于题目的数据范围很弱，我就直接再把并查集中的树的那个数组扫了一遍，找指向同一个父亲的节点数量最多的那个值，这就是最大的房间的大小。（其实我就是把并查集中的树的那个数组做了一个哈希排序，然后找里面的最大值）

至于移掉一块墙的最大的房间大小和这块墙的位置，我们可以枚举所有墙，首先一定判断墙的两边是否连通，连通的话就算了，不连通的话就有拆墙的价值，然后我们记下拆掉这块墙得到的新房间的最大面积就AC了。

Read full article from thecastle - codetrick