반응형
https://www.acmicpc.net/problem/20947
20947번: 습격받은 도시
$N$개의 줄에 도시의 정보를 출력한다. 각 줄은 $N$개의 문자를 포함하며 $i$번째 줄 $j$번째 문자는 도시의 세로 $i$번째 가로 $j$번째 칸에 대한 정보이다. 빈칸일 경우 ., 건물일 경우 O, 건물 잔해
www.acmicpc.net
접근법
1. 모든 .를 탐색하여 폭탄을 놓을 수 있는 곳에 놓기
=> 시간 초과
=> 모든 점 탐색(4,000,000) * 점 하나당 가로, 세로 검사(2,000 + 2,000)
=> 4,000,000*4,000
=> 16,000,000,000 (제한시간 3초)
2. 모든 .를 탐색하여 일단 폭탄을 다 놓고, O를 탐색하여 놓을 수 없는 위치의 폭탄 제거
=> 틀렸습니다
=> 잔해가 없는 곳에는 폭탄을 설치하면 안됨
3
...
...
...
3. 모든 X를 탐색하여 폭탄을 놓을 수 있는 위치에 놓고
모든 O를 탐색하여 놓을 수 없는 위치의 폭탄 제거
=> 맞았습니다!!
|
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
|
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n;
char arr[2001][2001];
void input();
void print();
void findX();
void findO();
void addBomb(int x, int y) {
// 우측
int i = y + 1;
while (arr[x][i] == '.')
arr[x][i++] = 'B';
// 좌측
i = y - 1;
while (arr[x][i] == '.')
arr[x][i--] = 'B';
// 위쪽
i = x - 1;
while (arr[i][y] == '.')
arr[i--][y] = 'B';
// 아래쪽
i = x + 1;
while (arr[i][y] == '.')
arr[i++][y] = 'B';
}
void removeBomb(int x, int y) {
// 우측
int i = y + 1;
while (arr[x][i] == 'B'|| arr[x][i] == '.')
arr[x][i++] = '.';
// 좌측
i = y - 1;
while (arr[x][i] == 'B'|| arr[x][i] == '.')
arr[x][i--] = '.';
// 위쪽
i = x - 1;
while (arr[i][y] == 'B'|| arr[i][y] == '.')
arr[i--][y] = '.';
// 아래쪽
i = x + 1;
while (arr[i][y] == 'B'|| arr[i][y] == '.')
arr[i++][y] = '.';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
findX();
findO();
print();
}
void input(){
cin >> n;
rep(i, n) {
rep(j, n)
cin >> arr[i][j];
}
}
void print(){
rep(i, n) {
rep(j, n)
cout << arr[i][j];
cout << '\n';
}
}
void findX(){
rep(i, n) {
rep(j, n) {
if (arr[i][j] == 'X')
addBomb(i, j);
}
}
}
void findO(){
rep(i, n) {
rep(j, n) {
if (arr[i][j] == 'O')
removeBomb(i, j);
}
}
}
|
cs |
반응형
