백준 17135번 캐슬 디펜스 C++

출처 : https://www.acmicpc.net/problem/17135

 

문제에 나와있는대로 구현을 하면 되는데 구현 난이도가 은근 높았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#include <bitset>

using namespace std;
using int64 = long long;

int n, m, d;
int Cnt = 0;
int ans = 0;

struct Pos {
    int row;
    int col;
    bool operator==(const Pos& other) const{
        if (row == other.row && col == other.col) return true;
        return false;
    }
    bool operator<(const Pos& other) const{
        return col < other.col;
    }
    bool operator>(const Pos& other) const{
        return col > other.col;
    }
};

vector<Pos> archers;
vector<Pos> enemies;
vector<Pos> enemies_Copy;

int GetDist(const Pos& archer, const Pos& enemy) {
    int ret = abs(archer.row - enemy.row) + abs(archer.col - enemy.col);
    return ret;
}

Pos FindEnemy(const Pos& archer) {
    int minDist = d;
    vector<Pos> shortestDistEnemies;
    for (auto a : enemies_Copy) {
        int dist = GetDist(archer, a);
        if (dist > minDist) continue;
        if (dist == minDist) shortestDistEnemies.push_back(a);
        else if (dist < minDist) {
            minDist = dist;
            shortestDistEnemies.clear();
            shortestDistEnemies.push_back(a);
        }
    }
    if (shortestDistEnemies.empty()) return { -1,-1 };
   
    sort(shortestDistEnemies.begin(), shortestDistEnemies.end());
    return { shortestDistEnemies.begin()->row,shortestDistEnemies.begin()->col };
}

void ShootArrow() {
    vector<Pos> findEnemies;
    for (auto a : archers) {
        findEnemies.push_back(FindEnemy(a));
    }
    for (auto a : findEnemies) {
        auto it = find(enemies_Copy.begin(), enemies_Copy.end(), a);
        if (it == enemies_Copy.end()) continue;
        Cnt++;
        enemies_Copy.erase(it);
    }
}

void MoveEnemy() {
    vector<Pos> passEnemies;
    for (int i = 0; i < enemies_Copy.size(); i++) {
        int nextRow = enemies_Copy[i].row + 1;
        if (nextRow >= n) {
            passEnemies.push_back({ nextRow,enemies_Copy[i].col });
        }
        enemies_Copy[i].row = nextRow;
    }
    for (auto a : passEnemies) {
        auto it = find(enemies_Copy.begin(), enemies_Copy.end(), a);
        enemies_Copy.erase(it);
    }
}

vector<int> idxes;
vector<bool> visited;

void BT(int idx, int cnt) {
    if (cnt >= 3) {
        archers.clear();
        enemies_Copy.clear();
        Cnt = 0;
        for (auto a : idxes) {
            archers.push_back({ n,a });
        }
        for (const auto& a : enemies) {
            enemies_Copy.push_back(a);
        }
        int turn = 1;
        while (true) {
            ShootArrow();
            MoveEnemy();
            if (enemies_Copy.empty()) break;
        }
        ans = max(ans, Cnt);
        return;
    }
    for (int i = idx; i < m; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        idxes.push_back(i);
        BT(i + 1, cnt + 1);
        visited[i] = false;
        idxes.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);

    cin >> n >> m >> d;
    visited = vector<bool>(m, false);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int input;
            cin >> input;
            if (input == 1)
                enemies.push_back({ i,j });
        }
    }

    BT(0, 0);

    cout << ans;
}