[SWEA] 5644. [모의 SW 역량테스트] 무선 충전

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int result;
int step[2][101];//이동경로
int dx[] = { 0,-1,0,1,0 };
int dy[] = { 0,0,1,0,-1 };
int ap[9][11][11];//ap의 정보들
queue <pair<int, int>> q;
void go(int m, int a) {
    int man0[] = { 1,1 };//출발 좌표
    int man1[] = { 10,10 };
    for (int i = 0; i <= m; i++) {
        man0[0] += dx[step[0][i]];//y
        man0[1] += dy[step[0][i]];//x
        man1[0] += dx[step[1][i]];//y
        man1[1] += dy[step[1][i]];//x
        int cnt0 = 0;
        int cnt1 = 0;
        int max0 = 0;
        int max1 = 0;
        int maxk0 = 0;//p가 제일쎈 ap
        int maxk1 = 0;
        int temp0[9] = { 0, };//충전범위에 닿는 ap들의 p를 다 넣는다.
        int temp1[9] = { 0, };
        for (int k = 0; k < a; k++) {
            if (ap[k][man0[0]][man0[1]] != 0) {
                temp0[cnt0] = ap[k][man0[0]][man0[1]];//temp0배열에 k번째 ap의 p 입력
                cnt0++;
                if (max0 < ap[k][man0[0]][man0[1]]) {
                    max0 = ap[k][man0[0]][man0[1]];//가장큰 ap의 p
                    maxk0 = k;//가장큰 ap 종류
                }
            }
            if (ap[k][man1[0]][man1[1]] != 0) {
                temp1[cnt1] = ap[k][man1[0]][man1[1]];
                cnt1++;
                if (max1 < ap[k][man1[0]][man1[1]]) {
                    max1 = ap[k][man1[0]][man1[1]];
                    maxk1 = k;
                }
            }
        }
        if (max0 == max1&&maxk0==maxk1) {//두 max가 같은 ap종류이면
            result += max0;//일단 p하나 입력
            if (cnt0 > 1 && cnt1 > 1) {//둘 다 범위 안에 있는 ap가 두개 이상이면
                sort(temp0, temp0 + cnt0, greater<int>());//내림차순 정렬 후
                sort(temp1, temp1 + cnt1, greater<int>());
                int temp = temp0[1] > temp1[1] ? temp0[1] : temp1[1];//두번째가 더큰 ap를 result에 더해준다
                result += temp;
            }
            else {
                if (cnt0 > 1) {//0번 사람이 범위 안에 있는 ap가 두개이상이면
                    sort(temp0, temp0 + cnt0, greater<int>());//내림차순 정렬 후
                    result += temp0[1];//두번째 녀석을 ap에 더해준다
                }
                if (cnt1 > 1) {
                    sort(temp1, temp1 + cnt1, greater<int>());
                    result += temp1[1];
                }
            }
        }
        else result = result + max0 + max1;//두 max가 다른 종류면 둘다result에 더해준다
    }
}
void bfs(int num, int c, int p) {//각각 ap마다 정보들 입력
    while (c--) {//c범위만큼 p퍼트린다
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int j = 1; j < 5; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx >= 1 && ny >= 1 && nx < 11 && ny < 11 && ap[num][nx][ny] == 0) {
                    ap[num][nx][ny] = p;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
    while (!q.empty()) q.pop();//큐초기화
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int test_case;
    cin >> test_case;
    for (int t = 1; t <= test_case; t++) {
        //start
        int m, a;
        int x, y, c, p;
        result = 0;
        cin >> m >> a;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> step[i][j];
            }
        }
        for (int i = 0; i < a; i++) {
            for (int j = 1; j < 11; j++) {
                for (int k = 1; k < 11; k++) {
                    ap[i][j][k] = 0;//초기화
                }
            }
            cin >> x >> y >> c >> p;
            q.push(make_pair(y, x));
            ap[i][y][x] = p;//bfs시작지점 미리 p로 입력
            bfs(i, c, p);
        }
        go(m, a);
        //end
        cout << '#' << t << ' ' << result << '\n';
    }
}