[SWEA 5650] 핀볼 게임
SW Expert Academy :: SWEA :: 5650 :: 핀볼게임
출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo
#include <bits/stdc++.h>
using namespace std;
struct S { int y, x, d; };
int T, N, tc, ans, A[102][102], dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 },
C[6][4] = { {},{2,3,1,0},{1,3,0,2},{3,2,0,1},{2,0,3,1},{2,3,0,1} }, D[5][5];
void G() {
for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
if (!A[i][j]) {
S n = { i,j }, z = n;
for (int dr = 0; dr < 4; dr++) {
int r = 0; n = z; n.d = dr;
while (1) {
n.y += dy[n.d], n.x += dx[n.d]; int p = A[n.y][n.x];
if (!p && !r) break;
if (A[n.y][n.x] < 0 || (z.y == n.y&&z.x == n.x)) break;
if (p) {
if (p < 6) n.d = C[p][n.d], r++;
else {
if (n.y == D[p % 6][1] && n.x == D[p % 6][2]) { n.y = D[p % 6][3], n.x = D[p % 6][4]; }
else { n.y = D[p % 6][1], n.x = D[p % 6][2]; }
}
}
} ans = max(ans, r);
}
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cin >> T;
while (T--) {
cin >> N; ans = 0; memset(D, 0, sizeof(D));
for (int i = 0; i < N + 2; i++) A[i][0] = A[0][i] = A[N + 1][i] = A[i][N + 1] = 5;
for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
cin >> A[i][j];
if (A[i][j] > 5) {
int l = A[i][j] % 6, k = D[l][0];
D[l][++k] = i, D[l][++k] = j; D[l][0] = k;
}
}
G();
cout << "#" << ++tc << " " << ans << '\n';
}
return 0;
}