[BOJ] 17135. 캐슬 디펜스

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

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int N,M,D;
	static int map[][];
	static boolean check[];
	static int arr[]=new int [3];
	static int cnt;
	static List<Point> list=new ArrayList<>();
	static List<Point> list2=new ArrayList<>();
	static List<Integer> del=new ArrayList<Integer>(); 
	static int maxH;
	static int ans=Integer.MIN_VALUE;
	static int size;
	public static void main(String[] args) {
		init();
		choose(0,0);
		System.out.println(ans);
	}
	
	public static void choose(int d,int st) {
		if(d==3) {
			cnt=0;
			for (int i = 0; i < size; i++) {
				list2.add(new Point(list.get(i).x,list.get(i).y));
			}
			int h=maxH;
			while(h++<N) {
				remove();
				down();
			}
			ans=Math.max(ans, cnt);
			list2.clear();
			return;
		}
		for (int i = st; i < M; i++) {
			if(!check[i]) {
				check[i]=true;
				arr[d]=i;
				choose(d+1,i);
				arr[d]=0;
				check[i]=false;
			}
		}
	}
	
	public static void down() {
		for (int i = list2.size()-1; i >=0 ; i--) {
			if(list2.get(i).x<N-1) {
				list2.get(i).x+=1;
			}else {
				list2.remove(list2.get(i));
			}
		}
	}
	
	public static void remove() {
		for (int i = 0; i < arr.length; i++) {
			int min=Integer.MAX_VALUE;
			int temp=Integer.MAX_VALUE;
			for (int j = 0; j < list2.size() ; j++) {
				int arrX=N;
				int arrY=arr[i];
				int pointX=list2.get(j).x;
				int pointY=list2.get(j).y;
				int dist=Math.abs(arrX-pointX)+Math.abs(arrY-pointY);
				if(dist>D) continue;
				if(min>dist) {
					temp=j;
					min=dist;
				}else if(min==dist) {
					if(list2.get(temp).y>pointY) {
						temp=j;
					}
				}
			}
			if(temp!=Integer.MAX_VALUE) {
				del.add(temp);
			}
		}
		Collections.sort(del);
		for (int i = del.size()-1; i >=0 ; i--) {
			if(i!=0 && del.get(i)==del.get(i-1)) continue;
			int temp=del.get(i);
			list2.remove(list2.get(temp));
			cnt++;
		}
		del.clear();
	}
	
	public static void init() {
		N=sc.nextInt();
		M=sc.nextInt();
		D=sc.nextInt();
		map=new int [N+1][M];
		check = new boolean [M];
		boolean flag=false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(sc.nextInt()==1) {
					list.add(new Point(i,j));
					if(!flag) {
						maxH=i;
						flag=true;
					}
				}
			}
		}
		size=list.size();
	}
	
	public static class Point{
		int x,y;
		Point(int x, int y){
			this.x=x;
			this.y=y;
		}
		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
	}
}