[swea 2382] 미생물 격리

분류 : 구현

 

요구사항

조건대로 구현하기

 

풀이

쉽게 구현하는 방법을 찾아야하는데

하드하게 n*n 행렬을 모두 탐색하며 구현도 해봤고

다른 풀이를 참조하여 미생물의 수만큼만 움직이면서 구현도 해봤다

 

문제를 푸는 방법은 많은거 같다

 

초반에 풀때 좀더 손 쉽게 풀 수 있는 방법을 찾는다면 좋다

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
struct go {
    int x;
    int y;
    int num;
    int dir;
    int alive;
};
int n, m, k;
go virus[1100];
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };
//0 최대 값, 1 최대 인덱스, 2 최대 인덱스의 num
int visit[110][110][4];
int ans = 0;
int get_dir(int d) {
    if (d == 1) return 2;
    else if (d == 2) return 1;
    else if (d == 3) return 4;
    else if (d == 4) return 3;
}
// 이동하면 거기에 어떤 놈이 있는가 확인
// 있으면 어느 놈이 최대이였는가 확인
// alive 최대가 아닌 놈 들은 alive를 0으로 바꿔주면된다
//
void solve() {
    int time = 0;
    while (true) {
        if (time == m)
            break;
        //이동
        for (int i = 0; i < k; i++) {
            if (virus[i].alive == 0) continue;
             
            int x = virus[i].x + dr[virus[i].dir];
            int y = virus[i].y + dc[virus[i].dir];
            int num = virus[i].num;
            virus[i].x = x;
            virus[i].y = y;
            if (x == 0 || y == 0 || x == n - 1 || y == n - 1) {
                virus[i].num = num / 2;
                virus[i].dir = get_dir(virus[i].dir);
                visit[x][y][2] += (num / 2);
                if (visit[x][y][0] < num) {
                    visit[x][y][0] = num;
                    visit[x][y][1] = i;
                     
                }
            }
            else {
                visit[x][y][2] += num;
                if (visit[x][y][0] < num) {
                    visit[x][y][0] = num;
                    visit[x][y][1] = i;
                     
                }
            }
        }
 
        for (int i = 0; i < k; i++) {
            if (virus[i].alive == 0) continue;
            int x = virus[i].x;
            int y = virus[i].y;
            int num = virus[i].num;
            if (visit[x][y][1] == i) {
                virus[i].num = visit[x][y][2];
            }
            else {
                virus[i].alive = 0;
            }
        }
        memset(visit, 0, sizeof(visit));
        /*
        for (int i = 0; i < k; i++) {
            cout << "i " <<i<<" "<< virus[i].x << " " << virus[i].y << " " << virus[i].num << " " << virus[i].dir << " " << virus[i].alive << endl;
        }
        cout << endl;
        */
        time++;
    }
    for (int i = 0; i < k; i++) {
        if (virus[i].alive == 1) {
            ans += virus[i].num;
        }
    }
}
int main() {
    int t;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        ans = 0;
        memset(visit, 0, sizeof(visit));
        memset(virus, 0, sizeof(virus));
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 0; i < k; i++) {
            int x, y, num, dir;
            scanf("%d%d%d%d", &virus[i].x, &virus[i].y, &virus[i].num, &virus[i].dir);
            virus[i].alive = 1;
        }
        solve();
        printf("#%d %d\n", tc, ans);
    }
}