5648. 원자 소멸 시뮬레이션

typedef struct
{
	int y, x, dir, k;
}info;

static int N;
static int board[4096][4096];
static int visit[4096][4096];
static int collision[4096][4096];
static int d[4][2] = {
	1, 0,
	-1, 0,
	0, -1,
	0, 1
};
static vector<info> vec;

static int solution()
{
	int x, y, dir, K, ret = 0;

	scanf("%d", &N);
	for (int cnt = 0; cnt < N; cnt++)
	{
		scanf("%d %d %d %d", &x, &y, &dir, &K);
		x += 1000; y += 1000;
		x *= 2; y *= 2;
		vec.push_back({ y, x, dir, K });
		visit[y][x] += 1;
	}

	int worst = 4002;
	for (int t = 0; t < worst; t++)
	{
		vector<info>::iterator itr = vec.begin();
		if (itr == vec.end())
			break;

		for (; itr != vec.end(); )
		{
			int & y = (*itr).y;
			int & x = (*itr).x;
			int dir = (*itr).dir;
			visit[y][x] -= 1; 
			
			y += d[dir][0]; x += d[dir][1];

			if (y < 0 || y > 4000 || x < 0 || x > 4000)
			{
				itr = vec.erase(itr);
			}
			else
			{
				visit[y][x] += 1;
				if (visit[y][x] > 1)
					collision[y][x] = 1;
				itr++;
			}
		}

		itr = vec.begin();
		for (; itr != vec.end(); )
		{
			int y = (*itr).y;
			int x = (*itr).x;
			if (collision[y][x] == 1)
			{
				if (visit[y][x] == 1)
					collision[y][x] = 0;
				visit[y][x] -= 1;
				ret += itr->k;
				itr = vec.erase(itr);
			}
			else
				itr++;
		}
	}

	vec.clear();
	return ret;
}

배열을 벗어나면 더 이상 충돌이 발생 할 수 없다.

거리차이가 홀수가 되면 n 과 n + 1 사이에서 만나야 되므로, 두배씩 늘려 주어야 한다.