[모의 SW 역량테스트] 미생물 격리.txt

////내 정답
////====미생물 격리
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

#include <stdio.h>
#include <queue>

using namespace std;

typedef struct micro {
	int w;
	int h;
	int direction;
	int num;
	bool isAlive;
	int ind;
}Micro;

Micro micro[1000];

int main()
{
	int nums;
	scanf("%d", &nums);

	for (int testcase = 1; testcase <= nums; testcase++)
	{
		int result = 0;
		int n, m, k;
		scanf("%d %d %d", &n, &m, &k);

		for (int i = 0; i < k; i++)
		{
			scanf("%d %d %d %d", &micro[i].w, &micro[i].h, &micro[i].num, &micro[i].direction);
			micro[i].isAlive = true;
			micro[i].ind = i;

		}

		for (int nowTime = 1; nowTime <= m; nowTime++)
		{
			int whole = 0;
			//이동
			for (int i = 0; i < k; i++)
			{
				if (micro[i].isAlive == false)
				{
					continue;
				}

				if (micro[i].direction == UP) micro[i].w -= 1;
				else if (micro[i].direction == DOWN) micro[i].w += 1;
				else if (micro[i].direction == LEFT) micro[i].h -= 1;
				else micro[i].h += 1;
			}

			//테두리 -> 죽이기
			for (int i = 0; i < k; i++)
			{
				if (micro[i].isAlive == false)
				{
					continue;
				}
				if (micro[i].w == 0 || micro[i].w == n-1 || micro[i].h == 0 || micro[i].h == n - 1)
				{
					if (micro[i].direction == UP) { micro[i].direction = DOWN; }
					else if (micro[i].direction == DOWN) { micro[i].direction = UP; }
					else if (micro[i].direction == LEFT) { micro[i].direction = RIGHT; }
					else { micro[i].direction = LEFT; }

					micro[i].num = micro[i].num / 2;
				}
			}
			//만난 경우 처리

			///////////////////////////////////////////////////////////////////////////////// 다시짜기
			//=> 미생물들만 확인할 것.
			
			for (int i = 0; i < k; i++)
			{
				if (micro[i].isAlive == false) { continue; }
				else
				{
					bool flag = false;
					int maxNum = 0;
					int sum = 0;
					Micro compare, max;
					queue <Micro> temp;
					temp.push(micro[i]);

					for (int j = i + 1; j < k; j++)
					{
						if (micro[j].isAlive == true && micro[j].w == micro[i].w &&micro[j].h == micro[i].h)
						{
							temp.push(micro[j]);
							flag = true;
						}
					}
					if (flag == true)
					{
						max = temp.front();
						temp.pop();

						sum += max.num;
						maxNum = max.num;

						//나머지 인자들 확인
						for (int test = 0; test < 4; test++)
						{
							if (temp.empty()) { break;}

							compare = temp.front();
							temp.pop();

							sum += compare.num;
							if (maxNum > compare.num)
							{
								micro[compare.ind].isAlive = false;
								micro[compare.ind].num = 0;
							}
							else
							{
								maxNum = compare.num;
								micro[max.ind].isAlive = false;
								micro[max.ind].num = 0;
								max = compare;
							}
						}

						micro[max.ind].num = sum;
						micro[max.ind].direction = max.direction;
					}
				}
			}
			
			for (int i = 0; i < k; i++)
			{
				whole += micro[i].num;	
			}
			result = whole;
		}
		printf("#%d %d\n", testcase, result);
	}
	return 0;
}






//////////////////////////////////////////////////////제한 시간 초과본
////====미생물
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

#include <stdio.h>
#include <queue>

using namespace std;

typedef struct micro {
	int w;
	int h;
	int direction;
	int num;
	bool isAlive;
	int ind;
}Micro;

Micro micro[1000];

int main()
{
	int nums;
	scanf("%d", &nums);

	for (int testcase = 1; testcase <= nums; testcase++)
	{
		int result = 0;
		int n, m, k;
		scanf("%d %d %d", &n, &m, &k);

		for (int i = 0; i < k; i++)
		{
			scanf("%d %d %d %d", &micro[i].w, &micro[i].h, &micro[i].num, &micro[i].direction);
			micro[i].isAlive = true;
			micro[i].ind = i;

		}

		for (int nowTime = 1; nowTime <= m; nowTime++)
		{
			int whole = 0;
			//이동
			for (int i = 0; i < k; i++)
			{
				if (micro[i].isAlive == false)
				{
					continue;
				}

				if (micro[i].direction == UP) micro[i].w -= 1;
				else if (micro[i].direction == DOWN) micro[i].w += 1;
				else if (micro[i].direction == LEFT) micro[i].h -= 1;
				else micro[i].h += 1;
			}

			//테두리 -> 죽이기
			for (int i = 0; i < k; i++)
			{
				if (micro[i].isAlive == false)
				{
					continue;
				}
				if (micro[i].w == 0 || micro[i].w == n-1 || micro[i].h == 0 || micro[i].h == n - 1)
				{
					if (micro[i].direction == UP) { micro[i].direction = DOWN; }
					else if (micro[i].direction == DOWN) { micro[i].direction = UP; }
					else if (micro[i].direction == LEFT) { micro[i].direction = RIGHT; }
					else { micro[i].direction = LEFT; }

					micro[i].num = micro[i].num / 2;
				}
			}
			//만난 경우 처리

			/////////////////////////////////////////////////////////////////////////////////
			for (int i = 1; i < n - 1; i++)
			{
				for (int j = 1; j < n - 1; j++)
				{
					bool flag = false;
					int maxNum = 0;
					int sum = 0;
					Micro compare, max;
					queue <Micro> temp;

					for (int number = 0; number < k; number++)
					{
						if (micro[number].isAlive == true && micro[number].w == i && micro[number].h == j)
						{
							temp.push(micro[number]);
							flag = true;
						}
					}
					if (flag == true) {
						max = temp.front();
						temp.pop();
						sum += max.num;
						maxNum = max.num;

						//나머지 인자들 확인
						for (int test = 0; test < 4; test++)
						{
							if (temp.empty()) { break; }

							compare = temp.front();
							temp.pop();

							if (maxNum > compare.num)
							{
								sum += compare.num;
								micro[compare.ind].isAlive = false;
								micro[compare.ind].num = 0;
							}
							else
							{
								sum += compare.num;
								maxNum = compare.num;
								micro[max.ind].isAlive = false;
								micro[max.ind].num = 0;
								max = compare;
							}
						}

						micro[max.ind].num = sum;
						micro[max.ind].direction = max.direction;
					}	
				}
			}

			for (int i = 0; i < k; i++)
			{
				whole += micro[i].num;	
			}
			result = whole;
		}
		printf("#%d %d\n", testcase, result);
	}
	return 0;
}


//////////다른 사람 정답
#include <iostream>
#include <cstring>
#include <cstdio>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M, K;
 
bool check[1000];
 
struct mic{
    int num;
    int dir;
    int maxnum;
};
 
mic a[100][100];
mic nexta[100][100];
 
int dx[] = {0, -1, 1, 0, 0 };
int dy[] = {0, 0, 0, -1, 1 };
 
int main(){
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++){
        cin >> N >> M >> K;
        memset(a, 0, sizeof(a));
 
        vector<pair<int, int>> micro(K);
        for (int i = 0; i < K; i++){
            int x, y, num, dir;
            cin >> x >> y >> num >> dir;
            a[x][y].num = num;
            a[x][y].dir = dir;
            a[x][y].maxnum = num;
        }
 
        while (M--){
            memset(nexta, 0, sizeof(nexta));
 
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    if (a[i][j].num != 0){
                        int x = i;
                        int y = j;
                        int dir = a[x][y].dir;
                        int num = a[x][y].num;
 
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];
                        if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1){
                            if (dir == 1) dir = 2;
                            else if (dir == 2) dir = 1;
                            else if (dir == 3) dir = 4;
                            else if (dir == 4) dir = 3;
 
                            nexta[nx][ny].num = num / 2;
                            nexta[nx][ny].dir = dir;
                            nexta[nx][ny].maxnum = nexta[nx][ny].num;
 
                            if (nexta[nx][ny].num == 0) nexta[nx][ny].dir = 0;
 
                        }
                        else {
                            if (nexta[nx][ny].maxnum == 0){
                                nexta[nx][ny].num = num;
                                nexta[nx][ny].dir = dir;
                                nexta[nx][ny].maxnum = num;
 
                            }
                            else{
                                if (nexta[nx][ny].maxnum != 0){
                                     
                                    if (nexta[nx][ny].maxnum > a[x][y].num){
                                        nexta[nx][ny].num += num;
                                    }
                                    else{
                                        nexta[nx][ny].num += num;
                                        nexta[nx][ny].dir = dir;
                                        nexta[nx][ny].maxnum = num;
                                    }
                                }
                            }
                        }
                    }
                }
            }
 
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    a[i][j].num = nexta[i][j].num;
                    a[i][j].dir = nexta[i][j].dir;
                    a[i][j].maxnum = nexta[i][j].maxnum;
                }
            }
        }
 
        long long ans = 0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (a[i][j].num != 0) ans += a[i][j].num;
            }
        }
 
        cout << "#" << tc << " " << ans << '\n';
    }
}