ZJU ACM 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));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
AS를 통한 Module 개발1. ModuleLoader 사용 2. IModuleInfo 사용 ASModuleOne 모듈...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.