[17135] 캐슬 디펜스

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

17135번: 캐슬 디펜스

같은 턴에서, 3번의 공격을 한번에 진행해주어야 한다. 만약 순차적으로 공격할 경우,

D=2일때 아래의 경우에서 0이 빈칸, 1이 적, 2가 궁수라고 보면

0 1
1 0
2 2

1번째 턴에서는 두 궁수가 모두 왼쪽 아래에 존재하는 적을 노리게 되도록 시뮬레이션이 되어야 하나

왼쪽의 궁수부터 적을 찾고, 해당 적을 제거해버리면 1번째 턴에 적을 2명을 제거하는 오류가 일어난다.
(두번째 궁수도 왼쪽 아래를 노려야 한다)

그외에는 맨해튼 거리, 정렬, next_permutation()으로 구현했다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, k, ans, a[16][16], Map[16][16];

bool d[16];

typedef struct {

    int dst, y, x;

} state;

void getTarget(vector<state>& v, int y, int x) {

    int i, j;

    for (i = 0; i < n; i++) {

        for (j = 0; j < m; j++) {

            if (Map[i][j] == 0) continue;

            int dst = abs(y - i) + abs(x - j);

            if (dst > k) continue;

            v.push_back({dst, i, j});

        }

    }

}

bool noEnemy(void) {

    for (int i = 0; i < n; i++)

        for (int j = 0; j < m; j++)

            if (Map[i][j] != 0) return false;

    return true;

}

void moveMap(void) {

    int i, j, tmp[16][16];

    memcpy(tmp, Map, sizeof(Map));

    memset(Map, 0, sizeof(Map));

    for (i = n - 1; i - 1 >= 0; i--)

        for (j = 0; j < m; j++) Map[i][j] = tmp[i - 1][j];

}

void getScore(void) {

    int i, j, score = 0;

    memcpy(Map, a, sizeof(a));

    while (1) {

        if (noEnemy()) break;

        vector<pi> tar;

        for (i = 0; i < m; i++) {

            if (!d[i]) continue;

            vector<state> v;

            getTarget(v, n, i);

            if (v.empty()) continue;

            sort(v.begin(), v.end(),

                 [](const state& A, const state& B) -> bool {

                     if (A.dst == B.dst) return A.x < B.x;

                     return A.dst < B.dst;

                 });

            tar.push_back({v.front().y, v.front().x});

        }

        for (auto& i : tar) {

            if (Map[i.first][i.second] == 1) {

                Map[i.first][i.second] = 0;

                score++;

            }

        }

        moveMap();

    }

    ans = max(score, ans);

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < m; j++) cin >> a[i][j];

    vector<int> base(m, 0);

    base[m - 1] = base[m - 2] = base[m - 3] = 1;

    do {

        memset(d, 0, sizeof(d));

        for (int i = 0; i < m; i++)

            if (base[i]) d[i] = true;

        getScore();

    } while (next_permutation(base.begin(), base.end()) == true);

    cout << ans;

    return 0;

}

---