#백준_17135 캐슬 디펜스 - Java 자바

# 유형 : 조합 using DFS + 시뮬레이션

# 난이도 : 골드 4

# 조합을 통해 궁수의 위치를 정한다. 정한 후, 조건에 맞게 사격, 남은 적들은 y칸들을 1씩 증가. 이 작업을 적이 다 죽거나 궁수 있는 곳까지 도달할 때까지 반복한다.

 

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p17135 {
    
    static int N,M,D, maxValue = Integer.MIN_VALUE;
    static int arr[][], cpArr[][], tmp[], ar[];
    static ArrayList<Point> enemy, set;
    
    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());
        
        arr = new int[N+1][M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        tmp = new int[M];
        ar = new int[3];
        for(int i=0; i<tmp.length; i++)
            tmp[i] = i;
        
        combination(0, 0);
        System.out.println(maxValue);
    }
    
    public static void combination(int len, int k) {
        
        if(len == 3) {
            enemy = new ArrayList<>();
            set = new ArrayList<>();
            cpArr = new int[N+1][M];
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    cpArr[i][j] = arr[i][j];
                    if(arr[i][j]==1)
                        enemy.add(new Point(j,i));
                }
            }
                
            
            for(int i=0; i<3; i++) {
                cpArr[N][tmp[ar[i]]] = -1;
                set.add(new Point(ar[i], N));
            }
            
            solve(cpArr);
            return;
        }
        
        if(k == M)
            return;
        
        ar[len] = tmp[k];
 
        combination(len+1, k+1);
        combination(len, k+1);
    }
    
    public static int getDist(Point p1, Point p2) {
        return Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y);
    }
 
    private static void solve(int[][] cpArr2) {
        // TODO Auto-generated method stub
        int result = 0;
        
        // 모든 적이 격자판에서 제외되면 게임이 끝난다. 
        while(!enemy.isEmpty()) {
            ArrayList<Point> remove = new ArrayList<>();
            for(int i=0; i<set.size(); i++) {
                int dir[] = new int[enemy.size()];
                int min = Integer.MAX_VALUE;
                
                //가장 가까운 적을 찾자
                for(int j=0; j<enemy.size(); j++) {
                    dir[j] = getDist(set.get(i), enemy.get(j));
                    min = Math.min(min, dir[j]);
                }
                
                ArrayList<Point> Possible = new ArrayList<>();
                for(int j=0; j<enemy.size(); j++) {
                    if(dir[j] == min && dir[j] <= D) {
                        Possible.add(enemy.get(j));
                    }
                }
                
                if(Possible.size() == 0) {
                    continue;
                }
                else if(Possible.size() == 1) {
                    remove.add(Possible.get(0));
                }
                // 2개 이상인 경우에는 가장 왼쪽
                else {
                    int minCol = 100;
                    for(int j=0; j<Possible.size(); j++) {
                        minCol = Math.min(minCol, Possible.get(j).x);
                    }
                    for(int j=0; j<Possible.size(); j++) {
                        if(Possible.get(j).x == minCol)
                            remove.add(Possible.get(j));
                    }
                    
                }
            }
            
            for(int i=0; i<remove.size(); i++){
                for(int j=0; j<enemy.size(); j++) {
                    if(remove.get(i).y == enemy.get(j).y && remove.get(i).x == enemy.get(j).x) {
                        enemy.remove(j);
                        result++;
                        break;
                    }
                }
            }
            
            int size = enemy.size();
            while(size>0) {
                if(enemy.get(0).y + 1 != N)
                    enemy.add(new Point(enemy.get(0).x, enemy.get(0).y+1));
                enemy.remove(0);
                size--;
            }
        }
        maxValue = Math.max(maxValue, result);
    }
}