[알고리즘] 백준 17135 - 캐슬 디펜스 (C++)

[문제 링크] : https://www.acmicpc.net/problem/17135

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, D;
int Map[16][16];
int Arr[16][16];
int Ans;

bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    if(a.second == b.second){
        return a.first.second < b.first.second;
    }
    return a.second < b.second; 
}

int shot(vector<int> &v){
    int ret = 0;
    int line = N;

    while(line > 0){
        vector<pair<int, int>> tmp;
        for(auto &at : v){
            vector<pair<pair<int, int>, int>> enemy;
            for(int i=0; i<line; i++){
                for(int j=0; j<M; j++){
                    if(Arr[i][j] == 0){
                        continue;
                    }
                    if(abs(i - line) + abs(j - at) > D){
                        continue;
                    }
                    enemy.push_back({{i, j}, abs(i - line) + abs(j - at)});
                }
            }

            if(enemy.empty() == true){
                continue;
            }
            sort(enemy.begin(), enemy.end(), comp);
            tmp.push_back({enemy[0].first.first, enemy[0].first.second});
        }

        for(auto &t : tmp){
            if(Arr[t.first][t.second] == 1){
                Arr[t.first][t.second] = 0;
                ret++;
            }
        }

        line--;
    }

    return ret;
}

void comb(int n, int pos, vector<int> &v){
    if(n == 3){
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                Arr[i][j] = Map[i][j];
            }
        }

        Ans = max(Ans, shot(v));
        return;
    }

    for(int i=pos; i<M; i++){
        v.push_back(i);
        comb(n + 1, pos + 1, v);
        v.pop_back();
    }
    return;
}

int main(){
    cin >> N >> M >> D;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> Arr[i][j];
            Map[i][j] = Arr[i][j];
        }
    }

    vector<int> archer;
    comb(0, 0, archer);

    cout << Ans << "\n";
    return 0;
}