USACO - 2.1.1 - The Castle

 

原创文章转载请注明出处

摘要：floodfill ， 图论

一. 题目翻译

1. 描述：

我们憨厚的USACO主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一份特别的礼物：一张“幸运爱尔兰”（一种彩票）。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡！ 喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作：比如说知道城堡有多少个房间，每个房间有多大。另外，农夫约翰想要把一面单独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。 你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。

城堡的平面图被划分成M*N(1 <=M,N<=50）个正方形的单位，一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。（就是说平面图的四周一定是墙。）

  # =墙壁 -,| = 没有墙壁 -> =指向一面墙，这面墙推掉的话我们就有一间最大的新房间

 

友情提示，这个城堡的平面图是7×4个单位的。一个“房间”的是平面图中一个由“#”、“-”、“|”围成的格子（就是图里面的那一个个的格子）。比如说这个样例就有5个房间。（大小分别为9、7、3、1、8个单位（排名不分先后））

移去箭头所指的那面墙，可以使2个房间合为一个新房间，且比移去其他墙所形成的房间都大。（原文为：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. ） 城堡保证至少有2个房间，而且一定有一面墙可以被移走。

 

2. 格式：

          INPUT FORMAT:

          第一行有两个整数：M和N 城堡的平面图用一个由数字组成的矩阵表示，一个数字表示一个单位，矩阵有N行M列。输入与样例的图一致。

          每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数的某个或某几个或一个都没有加起来的。

         1: 在西面有墙

         2: 在北面有墙

         4: 在东面有墙

         8: 在南面有墙

         城堡内部的墙会被规定两次。比如说（1，1）南面的墙，亦会被标记为（2，1）北面的墙。

          OUTPUT FORMAT:

          输出包含如下4行:

          第 1 行: 城堡的房间数目。

          第 2 行: 最大的房间的大小

          第 3 行: 移除一面墙能得到的最大的房间的大小

          第 4 行: 移除哪面墙可以得到面积最大的新房间。

          选择最佳的墙来推倒。有多解时选（重心）最靠西的（仍然有多解时选这些里面（重心）最靠南的）。（注：同一格子北边的墙比东边的墙重心更靠西） 用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（"N"（北）或者"E"（东））。

3. SAMPLE：

          SAMPLE INPUT:

 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

          SAMPLE OUTPUT:

5

9

16

4 1 E

   

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          这道题目的基础思路先是使用图论中的floodfill算法对城堡中所有房间进行着色，在同一个联通分支的房间有相同的颜色。然后依次遍历每个房间，尝试与该房间的东、南、西、北的房间合并，如果产生房间面积最大，则将结果记录并最后输出。

 

2. 具体实现（具体实现过程中出现的问题）：

          题目先对简单，请参考代码中的说明。

3. 需要注意的细节：

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

4. 启示：

         floodfill算法注意积累，题目中有多解时的判断条件一定要注意。有时间的话了解一下其他的解法。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:castle
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class castle {
	static int[][] colors;
	static int[][] walls;
	static int colNum;
	static int rowNum;
	static HashMap<Integer,Integer> counts;
	static int max;
	static int maxJoin;
	static String maxWall;
	
	public static void main(String[] args) {
		try {
//			Scanner in = new Scanner(System.in);
//			PrintWriter pw = new PrintWriter(System.out);
			
			Scanner in = new Scanner(new BufferedReader(new FileReader(
			"castle.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
			"castle.out")));
			
			 colNum = in.nextInt();
			 rowNum = in.nextInt();
			
			colors = new int[rowNum+2][colNum+2];
			walls = new int[rowNum+2][colNum+2];
			counts = new HashMap<Integer, Integer>();
			counts.put(0, 0);
			max = 0;
			int color = 1;
			
			for (int i=1;i<=rowNum;i++){
				for (int j=1;j<=colNum;j++){
					walls[i][j] = in.nextInt();
				}
			}
			
			for (int i=1;i<=rowNum;i++){
				for (int j=1;j<=colNum;j++){
					if (colors[i][j]==0){
						LinkedList<Node> ll = new LinkedList<Node>();
						ll.add(new Node(i,j));
						colors[i][j] = color;
						bfs(ll,color);
//						pw.println("after i = "+i+", j = "+j);
//						for (int k=1;k<=rowNum;k++){
//							for (int l=1;l<=colNum;l++){
//								pw.print(colors[k][l]+" ");
//							}
//							pw.println();
//						}
//						pw.println("count is : "+counts.get(colors[i][j]));
						color ++ ;
					}
				}
			}
			pw.println(color-1);
			pw.println(max);
			
			maxJoin = max;
			for (int j=1;j<=colNum;j++){
				for (int i=rowNum;i>=1;i--){
					if(colors[i][j]!=colors[i][j-1]){
						if (counts.get(colors[i][j])+counts.get(colors[i][j-1])>maxJoin){
							maxJoin = counts.get(colors[i][j])+counts.get(colors[i][j-1]);
							maxWall = i+" "+j+"W";
						}
					}
					
					if(colors[i][j]!=colors[i+1][j]){
						if (counts.get(colors[i][j])+counts.get(colors[i+1][j])>maxJoin){
							maxJoin = counts.get(colors[i][j])+counts.get(colors[i+1][j]);
							maxWall = i+" "+j+" S";
						}
					}
					
					if(colors[i][j]!=colors[i-1][j]){
						if (counts.get(colors[i][j])+counts.get(colors[i-1][j])>maxJoin){
							maxJoin = counts.get(colors[i][j])+counts.get(colors[i-1][j]);
							maxWall = i+" "+j+" N";
						}
					}
					
					if(colors[i][j]!=colors[i][j+1]){
						if (counts.get(colors[i][j])+counts.get(colors[i][j+1])>maxJoin){
							maxJoin = counts.get(colors[i][j])+counts.get(colors[i][j+1]);
							maxWall = i+" "+j+" E";
						}
					}
				}
			}
			pw.println(maxJoin);
			pw.println(maxWall);
			
			
			pw.close();
			
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		
	}
	
	public static void bfs(LinkedList<Node> ll, int color){
		int count = 0;
		while (ll.size()!=0){
			Node node = ll.removeFirst();
			int wall = walls[node.x][node.y];
			count ++;
			if (wall>=8){
				wall = wall - 8;
			} else {
				if(node.x+1<=rowNum){
					if (colors[node.x+1][node.y]==0){
						ll.add(new Node(node.x+1,node.y));
						colors[node.x+1][node.y]=color;
					}
				}
			}
			if (wall >=4){
				wall = wall -4;
			} else {
				if(node.y+1<=colNum){
					if (colors[node.x][node.y+1]==0){
						ll.add(new Node(node.x,node.y+1));
						colors[node.x][node.y+1]=color;
					}
				}
			}
			if (wall >=2){
				wall = wall -2;
			} else {
				if(node.x-1>=1){
					if (colors[node.x-1][node.y]==0){
						ll.add(new Node(node.x-1,node.y));
						colors[node.x-1][node.y]=color;
					}
				}
			}
			if (wall == 0){
				if(node.y-1>=1){
					if (colors[node.x][node.y-1]==0){
						ll.add(new Node(node.x,node.y-1));
						colors[node.x][node.y-1]=color;
					}
				}
			}
		}
		counts.put(color, count);
		if (count > max){
			max = count;
		}
	}
}

class Node{
	int x ;
	int y ;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}