ZJU ACM 1002

10231 단어 .net알고리즘J#
제목 은 여기 있 습 니 다.
 
 
 
 
 
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));
	}
}
 
 
 

                            

좋은 웹페이지 즐겨찾기