반응형
https://www.acmicpc.net/problem/2234
2234번: 성곽
문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을
www.acmicpc.net
서 : 1 , 북 : 10 , 동 : 100 , 남 : 1000 비트마스크 문제.
구역을 구하기위해 이중 포문으로 방문하면서 방의 개수를 구한다.
각각의 marking에 맞는 방의 개수를 구하느 cnt 배열을 만들어서 방의 크기를 저장한다.
-> 이값으로 가장 큰 방의 크기를 구해낸다.
방하나를 파괴한다는것은 서로다른 marking의 번호 방을 합친다는 뜻이다. for for 돌면서 오른쪽 밑 에 서로다른 marking의 방번호가 잇는 구역에 대해서 두개의 방 영역을 합한다.
|
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class B2234 {
static int map[][];
static int visit[][];
static int N, M;
static int dy[] = { 0, -1, 0, 1 };
static int dx[] = { -1, 0, 1, 0 };
static class Pair {
int y;
int x;
public Pair(int y, int x) {
super();
this.y = y;
this.x = x;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
visit = new int[N][M];
int cnt[] = new int[N * M + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int marking = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j] != 0)
continue;
marking++;
Queue<Pair> q = new LinkedList<>();
visit[i][j] = marking;
cnt[marking]++;
q.add(new Pair(i, j));
while (!q.isEmpty()) {
Pair tmp = q.poll();
for (int d = 0; d < 4; d++) {
if ((map[tmp.y][tmp.x] & (1 << d)) == (1 << d))
continue;
int ny = tmp.y + dy[d];
int nx = tmp.x + dx[d];
if (visit[ny][nx] != 0)
continue;
visit[ny][nx] = marking;
cnt[marking]++;
q.add(new Pair(ny, nx));
}
}
}
}
int maxValue = 0;
for(int i=1;i<=marking;i++) {
maxValue = Math.max(maxValue, cnt[i]);
}
int maxSum = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//옆
int ny = i;
int nx = j+1;
if(nx<M && visit[i][j]!=visit[ny][nx]) {
}
//밑
ny = i +1;
nx = j;
if(ny<N && visit[i][j]!=visit[ny][nx]) {
}
}
}
System.out.println(marking);
System.out.println(maxValue);
System.out.println(maxSum);
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형