핀볼 게임

Simulation

sol : 119' 49''

Learnings

• vector<pair<int, int>> wormholes[5];를 초기화하려면

for (int i = 0; i < 5; i++) {
	wormholes[i].clear();
}

이렇게 해주어야 한다. 지금의 wormholes->clear();는 wormholes[0].clear()와 같다. 즉, 첫 번째 벡터만 지워진다.

• 방향별 하드코딩을 할 때도 더 깔끔하게 할 수 있다.

int changeDir[6][4] = {
	{},
	{DOWN, RIGHT, UP, LEFT},   // 1번 블록
	{RIGHT, UP, DOWN, LEFT},   // 2번 블록
	{LEFT, UP, RIGHT, DOWN},   // 3번 블록
	{DOWN, LEFT, RIGHT, UP},   // 4번 블록
	{DOWN, UP, RIGHT, LEFT}    // 5번 블록
};

#include<iostream>
#include <climits>
#include <vector>
#include <tuple>

// Grid State Define
#define MAX_N 102
#define BLACKHOLE -1
#define EMPTY 0
#define WALL 11
// WORMHOLE : 6~10

// Direction Define
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
#define DIRECTION 4

using namespace std;

int n;
int grid[MAX_N][MAX_N];
int maxScore;

// 상, 하, 좌, 우
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

struct Ball {
	// 처음 i, j
	int ii;
	int ij;
	int i;
	int j;
	int score;
	int d;

	Ball() {}
	Ball(int _ii, int _ij, int _i, int _j, int _score, int _direction) :
		ii(_ii), ij(_ij), i(_i), j(_j), score(_score), d(_direction) {
	}
};

Ball ball;
vector<pair<int, int>> wormholes[5];

void InitGrid() {
	for (int i = 0; i <= MAX_N; i++) {
		for (int j = 0; j <= MAX_N; j++) {
			grid[i][j] = 0;
		}
	}
}

void Init() {
	wormholes->clear();
	InitGrid();

	cin >> n;

	for (int i = 0; i <= n + 1; i++) {
		grid[i][0] = WALL;
		grid[i][n + 1] = WALL;
	}

	for (int j = 0; j <= n + 1; j++) {
		grid[0][j] = WALL;
		grid[n + 1][j] = WALL;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
			if (6 <= grid[i][j] && grid[i][j] <= 10) {
				wormholes[grid[i][j] - 6].push_back(make_pair(i, j));
			}
		}
	}

	maxScore = INT_MIN;
}

// d : ball's current direction
void CollideOperation(int blockNum) {
	if (blockNum == 1) {
		if (ball.d == UP) ball.d = DOWN;
		else if (ball.d == DOWN) ball.d = RIGHT;
		else if (ball.d == LEFT) ball.d = UP;
		else if (ball.d == RIGHT) ball.d = LEFT;
	}
	else if (blockNum == 2) {
		if (ball.d == UP) ball.d = RIGHT;
		else if (ball.d == DOWN) ball.d = UP;
		else if (ball.d == LEFT) ball.d = DOWN;
		else if (ball.d == RIGHT) ball.d = LEFT;
	}
	else if (blockNum == 3) {
		if (ball.d == UP) ball.d = LEFT;
		else if (ball.d == DOWN) ball.d = UP;
		else if (ball.d == LEFT) ball.d = RIGHT;
		else if (ball.d == RIGHT) ball.d = DOWN;
	}
	else if (blockNum == 4) {
		if (ball.d == UP) ball.d = DOWN;
		else if (ball.d == DOWN) ball.d = LEFT;
		else if (ball.d == LEFT) ball.d = RIGHT;
		else if (ball.d == RIGHT) ball.d = UP;
	}
	else if (blockNum == 5 || blockNum == WALL) {
		if (ball.d == UP) ball.d = DOWN;
		else if (ball.d == DOWN) ball.d = UP;
		else if (ball.d == LEFT) ball.d = RIGHT;
		else if (ball.d == RIGHT) ball.d = LEFT;
	}
}

int Play(int i, int j, int d) {
	ball.ii = i, ball.ij = j, ball.d = d, ball.i = i, ball.j = j, ball.score = 0;

	while (true) {
		ball.i += ds[ball.d][0];
		ball.j += ds[ball.d][1];

		// 1. 블랙홀에 빠졌을 경우
		if (grid[ball.i][ball.j] == BLACKHOLE) {
			break;
		}

		// 2. 출발 위치로 돌아왔을 경우
		else if (ball.i == ball.ii && ball.j == ball.ij) {
			break;
		}

		// 3. 부딪혔을 경우 (블록 or 벽)
		else if ((1 <= grid[ball.i][ball.j] && grid[ball.i][ball.j] <= 5) || grid[ball.i][ball.j] == WALL) {
			// 점수를 올리며
			ball.score++;
			// 볼의 방향을 바꿔준다.
			CollideOperation(grid[ball.i][ball.j]);
		}

		// 4. 웜홀에 들어갔을 경우
		else if (6 <= grid[ball.i][ball.j] && grid[ball.i][ball.j] <= 10) {
			for (int h = 0; h < 2; h++) {
				int oppo_i, oppo_j;
				tie(oppo_i, oppo_j) = wormholes[grid[ball.i][ball.j] - 6][h];
				// 입구와 출구중 출구 좌표를 찾아서
				if (ball.i != oppo_i || ball.j != oppo_j) {
					ball.i = oppo_i, ball.j = oppo_j;
					break;
				}
			}
		}
	}

	return ball.score;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		Init();

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int d = 0; d < DIRECTION; d++) {
					if (grid[i][j] == EMPTY) {
						int curScore = Play(i, j, d);
						if (curScore > maxScore) {
							maxScore = curScore;
						}
					}
				}
			}
		}

		cout << "#" << test_case << " " << maxScore << '\n';
	}

	return 0;
}