BJ 17135現金防御

package day0408;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//https://www.acmicpc.net/problem/17135
public class CastleDefense {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N, M, D, numofM = 0, tnumofM, max = 0, numofKill;
	static int[] numbers;
	static int[][] map;
	static int[][] tmpmap;
	static int[][] dir = { { 0, -1, 0 }, { -1, 0, 1 } }; // 좌 상 우만 필요.

	static void func(int cnt, int start) {
		if (cnt == 3) {
			tnumofM = numofM;
			numofKill = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					tmpmap[i][j] = map[i][j];
				}
			}
			attack();			
			if(numofKill > max) max = numofKill;
			return;
		}
		for (int i = start; i < M; i++) {
			numbers[cnt] = i;
			func(cnt + 1, i + 1);
		}
	}

	static void attack() {
		while (tnumofM > 0) {
			for (int i = 0; i < 3; i++) {
				selectTarget(i);
			}
			eraseMonster();
			moveDown();
		}
	}

	static void selectTarget(int bow) {
		int startX = N - 1;
		int startY = numbers[bow];
		int startDist = 1;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { startX, startY, startDist });
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			if (tmpmap[cur[0]][cur[1]] >= 1) { // 가장가까운몬스터 ++한 후 리턴.
				tmpmap[cur[0]][cur[1]]++;
				return;
			}
			for (int d = 0; d < 3; d++) {
				int nx = cur[0] + dir[0][d];
				int ny = cur[1] + dir[1][d];
				int dist = cur[2];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || dist + 1 > D)
					continue;
				q.add(new int[] {nx, ny, dist + 1});
			}
		}

	}

	static void eraseMonster() {
		//System.out.println(Arrays.toString(numbers));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				//System.out.print(tmpmap[i][j] + " ");
				if (tmpmap[i][j] > 1) {
					tnumofM--;
					numofKill++;
					
					tmpmap[i][j] = 0;
				}
			}
			//System.out.println();
		}
		//System.out.println(numofKill);
	}

	static void moveDown() {
		for (int i = N - 1; i >= 0; i--) { // 역순으로 해줘야 덮어쓰지않을듯.
			for (int j = 0; j < M; j++) {
				if (tmpmap[i][j] == 1) {
					tmpmap[i][j] = 0;
					if (i + 1 < N) {
						tmpmap[i + 1][j] = 1;
					}
					if(i + 1 == N) {
						tnumofM--;
					}
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		numbers = new int[3];
		map = new int[N][M];
		tmpmap = 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());
				if (map[i][j] == 1) {
					numofM++;
				}
			}
		}
		func(0, 0);
		bw.append(max + "");
		bw.flush();
	}
}