5644. 무선 충전

시뮬레이션 문제다.

사람의 이동 경로가 주어지고 배터리 충전기의 개수와 위치, 강도, 범위가 주어질 때

이동 경로중에 충전 가능한 최대 배터리 양을 구하는 문제다.

배터리 충전기 개수가 8개밖에 안된다. 다음과 같은 방식으로 풀었다.

1. map[][]에 BC 번호에 따라 범위를 비트마스크로 표시한다. (굳이 비트마스크를 쓰지 않아도 된다.)

2. 사람을 옮긴다.

3. 각자의 map을 보고 만약 동일한 충전기의 범위 내라면 그걸 감안해서 계산하고 아니면 각자가 얻을 수 있는 최대값만을 구해서 더한다.

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
int a[101], b[101];
int map[11][11];
int dx[] = { 0,-1,0,1,0 }, dy[] = { 0,0,1,0,-1 };
int dxx[4][16] = {
    { -1,0,1,0 },
{ -2,-1,0,1,2,1,0,-1 },
{ -3,-2,-1,0,1,2,3,2,1,0,-1,-2 },
{ -4,-3,-2,-1,0,1,2,3,4,3,2,1,0,-1,-2,-3 }
};
int dyy[4][16] = {
    { 0,1,0,-1 },
{ 0,1,2,1,0,-1,-2,-1 },
{ 0,1,2,3,2,1,0,-1,-2,-3,-2,-1 },
{ 0,1,2,3,4,3,2,1,0,-1,-2,-3,-4,-3,-2,-1 }
};
pii d[256][256];
pii bc[256];
 
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t, n, m;
    int ans, i, j, k, x, y, c, p;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        ans = 0;
        cin >> n >> m;
        for (i = 1; i <= n; ++i) cin >> a[i];
        for (i = 1; i <= n; ++i) cin >> b[i];
        for (i = 1; i < 11; ++i) for (j = 1; j < 11; ++j) map[i][j] = 0;
        for (i = 0; i < m; ++i) {
            cin >> y >> x >> c >> p;
            bc[1 << i] = { tc,p };
            if (x >= 1 && y >= 1 && x < 11 && y < 11) map[x][y] |= (1 << i);
            for (j = 0; j < c; ++j) for (k = 0; k < ((j + 1) << 2); ++k) {
                if (x + dxx[j][k] >= 1 && x + dxx[j][k] < 11 && y + dyy[j][k] >= 1 && y + dyy[j][k] < 11)
                    map[x + dxx[j][k]][y + dyy[j][k]] |= (1 << i);
            }
        }
        int ax = 1, ay = 1, bx = 10, by = 10, jj = 0, kk = 0, mv[2];
        for (i = 0; i <= n; ++i) {
            ax += dx[a[i]]; ay += dy[a[i]];
            bx += dx[b[i]]; by += dy[b[i]];
            j = map[ax][ay];
            k = map[bx][by];
            if (d[j][k].first != tc) {
                mv[0] = 0;
                // 둘의 위치를 모두 포함하는 충전기가 하나라도 있다면
                if (j&k) {
                    for (; j; j -= jj) {
                        // a가 jj번째를 고르고
                        jj = j & -j;
                        for (k = map[bx][by]; k; k -= kk) {
                            // b가 kk번째를 골랐을 때
                            kk = k & -k;
                            if (jj&kk)        // 같은거라면 절반씩 먹으니 결국 bc[jj]의 총량만큼 충전가능
                                mv[0] = max(mv[0], bc[jj].second);
                            else            // 다른거라면 서로가 고른 배터리 용량만큼 충전가능
                                mv[0] = max(mv[0], bc[jj].second + bc[kk].second);
                        }
                    }
                }
                // 겹치는거 없음
                else {
                    // 각자 고를 수 있는 충전기중에 최대값만 고르면 된다
                    if (bc[j].first != tc) {
                        for (; j; j -= jj) {
                            jj = j & -j;
                            mv[0] = max(mv[0], bc[jj].second);
                        }
                        j = map[ax][ay];
                        bc[j] = { tc, mv[0] };
                    }
                    if (bc[k].first != tc) {
                        mv[1] = 0;
                        for (; k; k -= kk) {
                            kk = k & -k;
                            mv[1] = max(mv[1], bc[kk].second);
                        }
                        k = map[bx][by];
                        bc[k] = { tc, mv[1] };
                    }
                    mv[0] = bc[j].second + bc[k].second;
                }
                d[map[ax][ay]][map[bx][by]] = d[map[bx][by]][map[ax][ay]] = { tc,mv[0] };
            }
            ans += d[map[ax][ay]][map[bx][by]].second;
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}