Submission #169654

---

Source Code Expand

import java.util.Scanner;

public class Main {

	static int[] input;
	static int[][] field;
	static int[][] processField;
	static int w, h;
	static int cnt;
	static int max;

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		Scanner stdIn = new Scanner(System.in);


		w = stdIn.nextInt();
		h = stdIn.nextInt();

		field = new int[w][h];
		processField = new int[w][h];

		for(int i=0;i<w;i++){
			for(int j=0;j<h;j++){
				field[i][j] = -1;		// 金塊
			}
		}

		int n = stdIn.nextInt();

		int[] perm = new int[n];
		input = new int[n];
		boolean[] flag = new boolean[n];

		for(int i=1;i<=n;i++){
			field[stdIn.nextInt()-1][stdIn.nextInt()-1] = i;		// 装置
			input[i-1] = i;
		}

		max = 0;

		permutation(0, perm, flag);

		System.out.println(max);
	}

	private void output(int[] perm) {
		System.out.print("[\t");
		for(int value : perm){
			System.out.print(value+"\t");
		}
		System.out.println("]");
	}

	private void permutation(int idx, int[] perm, boolean[] flag) {
		if(idx==perm.length){
//			output(perm);
			copyField();
			process(perm);
			if(cnt>max){
				max = cnt;
			}
			cnt = 0;
			return;
		}
		for(int i=0;i<perm.length;i++){
			if(flag[i]) continue;
			perm[idx] = input[i];
			flag[i] = true;
			permutation(idx+1, perm, flag);
			flag[i] = false;
		}
	}

	private void copyField() {
		for(int i=0;i<w;i++){
			for(int j=0;j<h;j++){
				processField[i][j] = field[i][j];
			}
		}
	}

	private void process(int[] perm) {
		for(int i=0;i<perm.length;i++){
			int targetCrane = perm[i];
			for(int j=0;j<w;j++){
				for(int k=0;k<h;k++){
					if(targetCrane==processField[j][k]){
						collect(j, k);
					}
				}
			}
		}
	}

	private void collect(int j, int k) {
//		if(processField[j][k]==-1){
			cnt++;
			processField[j][k] = 0;
//		}

		// 右
		int idx = 0;
		while(true){
			idx++;
			if(j+idx<w&&processField[j+idx][k]==-1){
				cnt++;
				processField[j+idx][k] = 0;
			}
			else{
				break;
			}
		}
		// 左
		idx = 0;
		while(true){
			idx--;
			if(j+idx>=0&&processField[j+idx][k]==-1){
				cnt++;
				processField[j+idx][k] = 0;
			}
			else{
				break;
			}
		}
		// 右
		idx = 0;
		while(true){
			idx++;
			if(k+idx<h&&processField[j][k+idx]==-1){
				cnt++;
				processField[j][k+idx] = 0;
			}
			else{
				break;
			}
		}
		// 左
		idx = 0;
		while(true){
			idx--;
			if(k+idx>=0&&processField[j][k+idx]==-1){
				cnt++;
				processField[j][k+idx] = 0;
			}
			else{
				break;
			}
		}
	}
}

Submission Info

Judge Result