백준 17135 캐슬 디펜스 / java 자바

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

import java.util.*;
import java.io.*;

public class Main_캐슬디펜스 {
	static int N, M, D;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solve(0, 0);
		System.out.println(result);
	}
	static Stack<Integer> stack = new Stack<>();
	static int[][] temp;
	static int result = Integer.MIN_VALUE;
	
	static void solve(int cnt, int as) {
		if (cnt == 3) {
			result = Math.max(attack(), result);
			return;
		}
		for (int i = as; i < M; i++) {
			stack.push(i);
			solve(cnt + 1, i + 1);
			stack.pop();
		}
	}
	
	static int attack() {
		copy();
		int enemy = 0;
		while (ck()) {
			int[][] list = {{-1, -1}, {-1, -1}, {-1, -1}};
			int idx = 0;
			for (int s : stack) {
				int distance = D+1;
				for (int i = N-1; i >= 0; i--) {
					for (int j = 0; j < M; j++) {
						int compare = cal(i, j, s);
						if (temp[i][j] == 1 && compare <= D) {
							if (compare < distance) {
								list[idx][0] = i;
								list[idx][1] = j;
								distance = compare;
							} else if (compare == distance && j < list[idx][1]) {
								list[idx][0] = i;
								list[idx][1] = j;
							}
						}
					}
				}
				idx++;
			}
			boolean[][] ck = new boolean[N][M];
			for (int i = 0; i < 3; i++) {
				if (list[i][0] != -1) {
					temp[list[i][0]][list[i][1]] = 0;
					ck[list[i][0]][list[i][1]] = true;
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (ck[i][j]) enemy++;
				}
			}
			move();
		}
		return enemy;
	}
	static void move() {
		for (int j = 0; j < M; j++) {
			for (int i = N-1; i > 0; i--) {
				temp[i][j] = temp[i-1][j];
			}
			temp[0][j] = 0;
		}
	}
	static void copy() {
		temp = new int[N][];
		for (int i = 0; i < N; i++) {
			temp[i] = Arrays.copyOf(map[i], M);
		}
	}
	static boolean ck() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (temp[i][j] == 1) return true;
			}
		}
		return false;
	}
	static int cal(int r1, int c1, int c2) {
		return Math.abs(r1 - N) + Math.abs(c1 - c2);
	}
}