ZJU ACM 1002

题目在这里：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002

 

 

 

 

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	private static class Node{
		private int x;
		private int y;
		
		private List<Node> conflicts;
		
		private boolean isWall = false;
		private boolean isHasHouse = false;
		
		public Node(int x,int y,boolean isWall){
			this.x = x;
			this.y = y;
			this.isWall = isWall;
			
			this.conflicts = new ArrayList<Node>();
		}
		
		public int getConflicts(){
			return this.conflicts.size();
		}
		
		public void addConflict(Node node){
			this.conflicts.add(node);
		}
		
		public void removeConflict(Node node){
			this.conflicts.remove(node);
		}
		
		public void clearConflicts(){
			this.conflicts.clear();
		}
		
	}
	
	private static class City{
		int size;
		
		Node[][] nodes;
		
		public City(int size){
			this.size = size;
			this.nodes = new Node[this.size][this.size];
		}
		
		/**
		 * 得到最大房屋配置数量，使用贪婪算法。（某些输入不能得到正确结果）
		 * @return
		 */
		public int getMaxConfiguration(){
			return getSubMax(this.size);
		}
		
		/**
		 * 得到最大房屋配置数量，使用暴力法（非常暴力）。
		 * @return
		 */
		public int getMaxConfiguration2(){
			int max = 0;
			
			//得到所有可能的房屋设置配置信息
			List<int[]> cases = allCases(this.size*this.size);
			
			for(int[] setting:cases){
				this.init();
				
				this.applySetting(setting);
				
				//如果应用了房屋的配置信息后，城市的配置合法
				if(this.isLegal()){
					//得到所有的房屋数量
					int total = this.totalHouse();
					
					if(total > max)
						max = total;
				}
			}
			
			return max;
		}
		
		/**
		 * <p>该算法的思想是：首先将所有非墙节点设置为房屋，然后计算每一个房屋的冲突节点列表（该列表是城市中所有与该房屋冲突的节点集合）。
		 * 然后不断循环下面的步骤：
		 * 
		 * <pre>
		 * 找出有最大冲突数（冲突节点列表的size）的那个节点，将该节点设置为非房屋，判断此时城市是否合法，如果合法，则返回此时城市的房屋数量。
		 * 
		 * @return
		 */
		public int getMaxConfiguration3(){
			//将所有非墙节点设置为房屋
			for(int i = 0; i < this.size; i++){
				for(int j = 0; j < this.size; j++){
					Node cur = nodes[i][j];
					if(!cur.isWall) cur.isHasHouse = true;
					
					cur = nodes[j][i];
					if(!cur.isWall) cur.isHasHouse = true;
				}
			}
			
			//计算每个房屋的冲突房屋列表
			for(int i = 0; i < this.size; i++){
				for(int j = 0; j < this.size; j++){
					Node cur = nodes[i][j];
					if(cur.isWall)	continue;
					
					for(int k = j+1; k < this.size; k++){
						if(nodes[i][k].isWall) break;
						
						cur.addConflict(nodes[i][k]);
						nodes[i][k].addConflict(cur);
					}
				}
			}
			
			for(int i = 0; i < this.size; i++){
				for(int j = 0; j < this.size; j++){
					Node cur = nodes[j][i];
					if(cur.isWall)	continue;
					
					for(int k = j+1; k < this.size; k++){
						if(nodes[k][i].isWall) break;
						
						cur.addConflict(nodes[k][i]);
						nodes[k][i].addConflict(cur);
					}
				}
			}
			
			int totalHouse = this.totalHouse();
			
			if(this.isLegal())	return totalHouse;
			
			while(true){
				int max = 0;
				
				Node maxConflict = null;
				
				//下面找最大冲突数的那个节点
				for(int i = 0; i < this.size; i++){
					for(int j = 0; j <this.size; j++){
						Node cur = nodes[i][j];
						if(cur.isHasHouse && !cur.isWall && cur.getConflicts() > max){
							max = cur.getConflicts();
							maxConflict = cur;
						}
						cur = nodes[j][i];

						if(cur.isHasHouse && !cur.isWall && cur.getConflicts() > max){
							max = cur.getConflicts();
							maxConflict = cur;
						}
					}
				}
				
				//如果找到了最大冲突数的节点，则设置该节点的房屋属性为false，并且更新该节点冲突节点列表里德哪些节点
				if(maxConflict != null){
					for(Node node:maxConflict.conflicts)
						node.removeConflict(maxConflict);
					
					maxConflict.isHasHouse = false;
					maxConflict.clearConflicts();
					
				}
				
				if(this.isLegal()){
					totalHouse = this.totalHouse();
					return totalHouse;
				}
			}
			
		}
		
		/**
		 * 将房屋的设置信息应用到城市上，根据setting数组中位置的房屋设置，来设置每一个节点是否为房屋
		 * @param setting
		 */
		private void applySetting(int[] setting){
			int total = this.size * this.size;
			for(int i = 0; i < total; i++){
				int row = i/this.size;
				int column = i%this.size;
				
				if(!nodes[row][column].isWall){
					nodes[row][column].isHasHouse = (setting[i]==1);
				}
			}
		}
		
		/**
		 * 得到当前城市的房屋数量
		 * @return
		 */
		private int totalHouse(){
			int houses = 0;
			for(int i = 0; i < this.size; i++){
				for(int j = 0; j < this.size; j++){
					if(this.nodes[i][j].isHasHouse) houses++;
				}
			}
			
			return houses;
		}
		
		/**
		 * 初始化房屋设置，将所有非墙节点的isHouse设置为false
		 */
		private void init(){
			for(int i = 0; i < this.size; i++){
				for(int j = 0; j <this.size; j++){
					nodes[i][j].isHasHouse = false;
				}
			}
		}
		
		/**
		 * 判断当前房屋配置是否合法
		 * @return
		 */
		private boolean isLegal(){
			return this.isSubLegal(this.size);
		}
		
		public int getSubMax(int n){
			if(n == 1){
				if(nodes[0][0].isWall){
					return 0;
				}else{
					nodes[0][0].isHasHouse = true;
					return 1;
				}
			}
			
			
			int subMax = getSubMax(n-1);
			
			int max = subMax;
			for(int i = 0; i < n;i++){
				Node node = nodes[n-1][i];
				if(!node.isWall){
					if(node.isHasHouse)	continue;
					node.isHasHouse = true;
					if(!isSubLegal(n)){
						node.isHasHouse = false;
					}else{
						max++;
					}
				}
			}
			
			for(int i = 0; i < n; i++){
				Node node = nodes[i][n-1];
				if(!node.isWall){
					if(node.isHasHouse)	continue;
					node.isHasHouse = true;
					if(!isSubLegal(n)){
						node.isHasHouse = false;
					}else{
						max++;
					}
				}
			}
			
			return max;
		}
		
		private boolean isSubLegal(int n){
			boolean isLegal = true;
			for(int i = 0;i < n;i++){
				boolean presiousHasHouse = false;
				for(int j = 0; j < n;j++){
					Node node = nodes[i][j];
					if(node.isWall){
						presiousHasHouse = false;
					}else{
						if(presiousHasHouse){
							if(node.isHasHouse)
								return false;
						}else{
							if(node.isHasHouse)
								presiousHasHouse = true;
						}
					}
				}
			}
			
			for(int i = 0;i < n;i++){
				boolean presiousHasHouse = false;
				for(int j = 0; j < n;j++){
					Node node = nodes[j][i];
					if(node.isWall){
						presiousHasHouse = false;
					}else{
						if(presiousHasHouse){
							if(node.isHasHouse)
								return false;
						}else{
							if(node.isHasHouse)
								presiousHasHouse = true;
						}
					}
				}
			}
			
			return isLegal;
		}
		
		private static List<int[]> allCases(int n){
			if(n == 1){
				List<int[]> results = new ArrayList<int[]>();
				results.add(new int[]{0});
				results.add(new int[]{1});
				
				return results;
			}
			
			List<int[]> subData = allCases(n-1);
			List<int[]> results = new ArrayList<int[]>();
			
			for(int[] subs:subData){
				int[] data = new int[n];
				data[n-1] = 0;
				for(int i = 0; i< subs.length;i++)
					data[i] = subs[i];
				
				results.add(data);
			}
			
			for(int[] subs:subData){
				int[] data = new int[n];
				data[n-1] = 1;
				for(int i = 0; i< subs.length;i++)
					data[i] = subs[i];
				
				results.add(data);
			}
			
			return results;
		}
	}
	
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		
		List<City> citys = new ArrayList<City>();
		
		int cityLine = 0;
		City currentCity = null;
		while(scanner.hasNextLine()){
			String line = scanner.nextLine();
			if("0".equals(line)){
				if(currentCity != null)
					citys.add(currentCity);
				
				break;
			}
			
			//新城市的开始
			if(line.length() == 1){
				if(currentCity != null)
					citys.add(currentCity);
				
				cityLine = 0;
				currentCity = new City(Integer.valueOf(line));
			}else{
				for(int i = 0;i < currentCity.size; i++){
					char nodeChar = line.charAt(i);
					boolean isWall = false;
					if(nodeChar == 'X'){
						isWall = true;
					}
					
					currentCity.nodes[cityLine][i] = new Node(cityLine,i,isWall);
				}
				
				cityLine++;
			}
		}
		
		long start = System.currentTimeMillis();
		
		for(City city:citys)
			System.out.println(city.getMaxConfiguration3());
		
		System.out.println("计算用时："+(System.currentTimeMillis() - start));
	}
}