삼성 5650 핀볼 게임

0인 곳에서 총 4방향에 대해서 dfs를 돌리면서 시작점에 왔을 때와 블랙홀에 빠졌을 때까지의 score의 최댓값을 구할 수 있다

 

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

깃허브주소: https://github.com/surinoel/boj/blob/master/swea5650.cpp

 

	#include <cstdio>
	#include <vector>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	int mat[100][100];
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	int block[6][4] = {
	{ 0, 0, 0, 0 },
	{ 2, 0, 3, 1 },
	{ 1, 2, 3, 0 },
	{ 1, 3, 0, 2 },
	{ 3, 0, 1, 2 },
	{ 1, 0, 3, 2 }
	};
	int n;
	int ans;
	int sx, sy;
	vector<pair<int, int>> hole[11];
	void go(int dir, int x, int y, int score) {
	int tx = x + dx[dir];
	int ty = y + dy[dir];
	if (tx < 0 || ty < 0 || tx > n - 1 || ty > n - 1) {
	ans = max(ans, score * 2 + 1);
	}
	else if (tx == sx && ty == sy) {
	ans = max(ans, score);
	}
	else if (mat[tx][ty] == 0) {
	go(dir, tx, ty, score);
	}
	else if (mat[tx][ty] >= 1 && mat[tx][ty] <= 5) {
	int ddir = block[mat[tx][ty]][dir];
	go(ddir, tx, ty, score + 1);
	}
	else if (mat[tx][ty] >= 6 && mat[tx][ty] <= 10) {
	int h = mat[tx][ty];
	for (int i = 0; i < hole[h].size(); i++) {
	int hx = hole[h][i].first;
	int hy = hole[h][i].second;
	if (hx != tx || hy != ty) {
	go(dir, hx, hy, score);
	break;
	}
	}
	}
	else if (mat[tx][ty] == -1) {
	ans = max(ans, score);
	}
	return;
	}
	int main(void) {
	int tc;
	scanf("%d", &tc);
	for (int test_case = 1; test_case <= tc; test_case++) {
	memset(mat, 0, sizeof(mat));
	for (int i = 6; i <= 10; i++) {
	hole[i].clear();
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	scanf("%d", &mat[i][j]);
	if (mat[i][j] >= 6 && mat[i][j] <= 10) {
	hole[mat[i][j]].push_back(make_pair(i, j));
	}
	}
	}
	ans = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (mat[i][j] != 0) continue;
	sx = i, sy = j;
	for (int k = 0; k < 4; k++) {
	go(k, i, j, 0);
	}
	}
	}
	printf("#%d %d\n", test_case, ans);
	}
	return 0;
	}

view raw swea5650.cpp hosted with ❤ by GitHub