[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][5650번] 핀볼 게임

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct q_info{
    int X;
    int Y;
};
struct {
    int X;
    int Y;
    int C;
    int P;
}charge_device[9];
 
struct {
    vector<int> charge_device_num;
}map[11][11];
 
int ans;
int A, M, C, P;
int A_foot[101];
int B_foot[101];
queue<q_info> A_person;
queue<q_info> B_person;
int p_x[5] = { 0,0,1,0,-1 };
int p_y[5] = { 0,-1,0,1,0 };
bool visited[11][11];
 
void print() {
    /*cout << endl;
    for (register int Y = 1; Y <= 10; Y++) {
        for (register int X = 1; X <= 10; X++) {
            if (X == B_person.front().X && Y == B_person.front().Y)
                cout << "1 ";
            else {
                cout << "0 ";
            }
        }
        cout << endl;
    }*/
    cout << endl;
    for (register int Y = 1; Y <= 10; Y++) {
        for (register int X = 1; X <= 10; X++) {
            cout << map[Y][X].charge_device_num.size()<<" ";
            }
        cout << endl;
        }
        
}
 
void init() {
    ans = 0;
    while (!A_person.empty()) 
        A_person.pop();
    while (!B_person.empty())
        B_person.pop();
    
    for (register int Y = 1; Y <= 10; Y++) {
        for (register int X = 1; X <= 10; X++) {
            map[Y][X].charge_device_num.clear();
            visited[Y][X] = false;
        }
    }
    for (register int i = 1; i <= 9; i++) {
        charge_device[i].C = 0;
        charge_device[i].P = 0;
        charge_device[i].X = 0;
        charge_device[i].Y = 0;
    }
    q_info INIT;
    INIT.X = 1;
    INIT.Y = 1;
    A_person.push(INIT);
    INIT.X = 10;
    INIT.Y = 10;
    B_person.push(INIT);
}
 
void check() {
    cout << "1,1" << endl;
    int aend = map[1][1].charge_device_num.size();
    for (register int i = 0; i < aend; i++) {
        int temp = charge_device[map[1][1].charge_device_num[i]].P;
        cout << temp << endl;
    }
    cout << "10,10" << endl;
    int end = map[10][10].charge_device_num.size();
    for (register int i = 0; i < end; i++) {
        int temp = charge_device[map[10][10].charge_device_num[i]].P;
        cout << temp << endl;
    }
}
 
void walk() {
    int time = 0;
    if (map[1][1].charge_device_num.size() != 0) {
        int end = map[1][1].charge_device_num.size();
        int temp=0;
        for (register int i = 0; i < end; i++) {
            if (temp < charge_device[map[1][1].charge_device_num[i]].P)
            temp = charge_device[map[1][1].charge_device_num[i]].P;
        }
        ans += temp;
    }
    if (map[10][10].charge_device_num.size() != 0) {
        int end = map[10][10].charge_device_num.size();
        int temp = 0;
        for (register int i = 0; i < end; i++) {
            if (temp< charge_device[map[10][10].charge_device_num[i]].P)
            temp = charge_device[map[10][10].charge_device_num[i]].P;
        }
        ans += temp;
    }
    while (1) {//제한 시간만큼
        //print();
        time++;
        if (time == M) break; //시간이 다되면 종료
        q_info A_cur = A_person.front();
        q_info B_cur = B_person.front();
        A_person.pop();
        B_person.pop();
        int anx = p_x[A_foot[time]] + A_cur.X;
        int bnx = p_x[B_foot[time]] + B_cur.X;
        int any = p_y[A_foot[time]] + A_cur.Y;
        int bny = p_y[B_foot[time]] + B_cur.Y;
        int Aend = map[any][anx].charge_device_num.size(); //현재 위치에서 충전이 가능한지 알아보는 것 //210번줄의 코드가 필요한 이유
        int Bend = map[bny][bnx].charge_device_num.size();
        q_info Anext;
        Anext.X = anx;
        Anext.Y = any;
        A_person.push(Anext);
        q_info Bnext;
        Bnext.X = bnx;
        Bnext.Y = bny;
        B_person.push(Bnext);
        vector<int> Av;
        vector<int> Bv;
 
        if (Aend == 0 && Bend == 0) continue; //충전이 불가능하다면 통과
        if (Aend > 0) { //충전이 가능하다면
            for (register int i = 0; i < Aend; i++)
                Av.push_back(map[any][anx].charge_device_num[i]); //위치에서 충전가능한 충전기의 번호를 모두 저장
        }
        if (Bend > 0) {
            for (register int i = 0; i < Bend; i++)
                Bv.push_back(map[bny][bnx].charge_device_num[i]); //위치에서 충전가능한 충전기의 번호를 모두 저장
        }
            int ch = 0; int ch_temp = 0;
            if (Av.size() > 0 && Bv.size() > 0) { //A와 B에서 둘다 충전이 가능한경우 같은 충전기를 사용하는지 알아보기 위한 로직
                for (register int av = 0; av < Av.size(); av++) {
                    ch_temp = 0;
                    for (register int bv = 0; bv < Bv.size(); bv++) {
                        if (Av[av] == Bv[bv]) { //같은 충전기를 사용한다면
                            ch_temp += charge_device[Av[av]].P;
                        }
                        else { //다른 충전기를 사용한다면
                            ch_temp += charge_device[Av[av]].P;
                            ch_temp += charge_device[Bv[bv]].P;
                        }
                        if (ch < ch_temp) //가장 큰것을 저장
                            ch = ch_temp;
                        ch_temp = 0;
                    }
                }
                ans += ch;
            }
            else if((Av.size()>0&&Bv.size()==0)||(Av.size()==0 && Bv.size() > 0)) { //둘줄 하나만 가능한경우 가장 충전을 많이 시켜주는 곳을 충전시킴
                if (Av.size() > 0) {
                    int end = Av.size();
                    int temp = 0;
                    for (register int i = 0; i < end; i++) {
                        if (temp < charge_device[Av[i]].P)
                            temp = charge_device[Av[i]].P;
                    }
                    ans += temp;
                }
                if (Bv.size() > 0) {
                    int end = Bv.size();
                    int temp = 0;
                    for (register int i = 0; i < end; i++) {
                        if (temp < charge_device[Bv[i]].P)
                            temp = charge_device[Bv[i]].P;
                    }
                    ans += temp;
                }
                    
                
            }
        Av.clear(); 
        Bv.clear();
 
    }
}
 
void device_pos() {
    queue<q_info>device_q;
    for (register int i = 1; i <= A; i++) {
        while (!device_q.empty())
            device_q.pop();
        for (register int Y = 1; Y <= 10; Y++) {
            for (register int X = 1; X <= 10; X++) {
                visited[Y][X] = false;
            }
        }
        q_info pos;
        pos.X = charge_device[i].X;
        pos.Y = charge_device[i].Y;
        visited[pos.Y][pos.X] = true;
        device_q.push(pos);
        int end = charge_device[i].C;
        while (end--) {// 충전기의 범위 만큼 bfs를 돌려주기 위해서 
            int q_end = device_q.size();
            for (register int j = 0; j < q_end; j++) {
                q_info cur = device_q.front();
                device_q.pop();
                for (register int dis = 1; dis <= 4; dis++) {
                    int nx = cur.X + p_x[dis];
                    int ny = cur.Y + p_y[dis];
                    if (nx > 0 && nx < 11 && ny > 0 && ny < 11 && !visited[ny][nx]) { //범위 안이고 방문학적이 없을때 
                        visited[ny][nx] = true;
                        map[ny][nx].charge_device_num.push_back(i);// 충전기의 번호를 저장해줌
                        q_info next;
                        next.X = nx;
                        next.Y = ny;
                        device_q.push(next);
                    }//범위안
                }// 4방향
            } //q의 크기만큼만
        }//while
    }//for
    //print();
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int T;
    scanf("%d", &T);
    //cin >> T;
    for (register int t = 1; t <= T; t++) {
        init();
        scanf("%d %d", &M, &A);
        
        for (register int m = 1; m <= M; m++) 
            scanf("%d", &A_foot[m]);
        for (register int m = 1; m <= M; m++) 
            scanf("%d", &B_foot[m]);
        int x, y;
 
        for (register int a = 1; a <= A; a++) {
            scanf("%d %d %d %d", &x, &y, &C, &P);
            charge_device[a].C = C;
            charge_device[a].P = P;
            charge_device[a].X = x;
            charge_device[a].Y = y;
            map[y][x].charge_device_num.push_back(a);
        }
        M++; //위에서 while문을 돌리기 위해 1을 추가 시켜줌
        device_pos(); // 충전기의 범위
        //check();
        //print();
        walk(); //A와B가 걷기
        //printf("#%d %d\n", t, ans);
        cout << "#" << t << " " << ans << endl;
    }
 
}