알고리즘/알고리즘 문제
[삼성 swea] 5650. 핀볼 게임
charminseok
2019. 9. 13. 16:01
map에서 0인곳에서 시작지점을 잡고 4방향으로 검색을 해줬다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include<iostream>
#include<vector>
using namespace std;
int n;
int ans;
vector<vector<int>> map;
vector<vector<bool>> visit;
vector<vector<pair<int, int>>> WH;
int dxy[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//오,왼,아래,위
int nxtd[4][5] = { {1,1,2,3,1}, {3,2,0,0,0}, { 0, 3, 3, 1, 3 }, { 2,0,1,2,2 } };
void go(int a,int b, int di) {
int tmp = 0;
int starta = a;
int startb = b;
while (true) {
a += dxy[di][0];
b += dxy[di][1];
if (a < 0 || a >= n || b < 0 || b >= n) {
tmp++;
if (di == 0 || di == 2)
di++;
else if (di == 1 || di == 3)
di--;
continue;
}
if (map[a][b] == -1 || a == starta && b == startb) {
break;
}
if (map[a][b] >= 1 && map[a][b] <= 5) {
di = nxtd[di][map[a][b] - 1];
tmp++;
}
else if (map[a][b] >= 6 && map[a][b] <= 10) {
int ta = a;
int tb = b;
if (a == WH[map[a][b] - 6][0].first && b == WH[map[a][b] - 6][0].second) {
ta = WH[map[a][b] - 6][1].first;
tb = WH[map[a][b] - 6][1].second;
a = ta;
b = tb;
}
else {
ta = WH[map[a][b] - 6][0].first;
tb = WH[map[a][b] - 6][0].second;
a = ta;
b = tb;
}
}
}
ans = ans > tmp ? ans : tmp;
}
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> n;
ans = 0;
WH.assign(5,vector<pair<int,int>>());
map.assign(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
if (map[i][j] > 5 && map[i][j] < 11)
WH[map[i][j] - 6].push_back({ i,j });
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) {
for (int d = 0; d < 4; d++)
go(i, j, d);
}
}
}
cout << "#" << t << " " << ans << endl;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|