#2583: 지역 찾기
문제 )
크기가 M×N(M, N≤100)인 모눈종이가 있고 눈금 분할이 1입니다. 이 모눈종이의 눈금에 따라 K개의 사각형을 그리면 나머지 K개의 사각형은 여러 개의 영역으로 나누어집니다. 내부를 제외하고.
예를 들어 모눈종이에 다음과 같이 M=5, N=7인 사각형 3개를 그린다면
.png?type=w800 "고주파 리프팅 종류와 디의원의 리프팅")
에서와 같이
M, N, K, K 사각형의 좌표가 주어졌을 때 K 사각형의 내부를 제외한 나머지 영역을 몇 개의 개별 영역으로 분할하고 분할된 각 영역의 면적을 계산하는 프로그램을 작성하십시오. , 그리고 그들을 발행
입력:
첫 번째 줄에는 M, N, K가 공백을 두고 차례로 지정됩니다. M, N, K는 모두 100 이하의 자연수이다. 두 번째 행부터 K개의 행에서 x, y 좌표 값은 사각형의 왼쪽 하단 모서리이고 x, y 좌표 값은 사이에 공간이 지정된 공간이 있는 직사각형의 오른쪽 상단 모서리입니다. 모눈종이의 왼쪽 아래 꼭지점 좌표는 (0,0)이고 오른쪽 위 꼭짓점 좌표는 (N,M)입니다. 입력된 K-직사각형이 모눈종이 전체를 채우는 경우는 없습니다.
누르다 :
분할된 영역의 수는 첫 번째 줄에 출력됩니다. 두 번째 줄에는 각 범위의 범위가 오름차순으로 정렬되고 그 사이에 공백이 인쇄됩니다.
설명)
평소에 BFS를 하기 때문에 최단 거리를 찾는 것처럼 문제를 풀었습니다.
답을 찾는 데 시간이 좀 걸렸습니다.
|
하나
2
삼
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
|
#포함하다 <iostream>
#포함하다 <벡터>
#포함하다 <연산>
#포함하다 <대기줄>
사용 네임스페이스 기본;
내부 m, n, k, 온도;
벡터<벡터<내부>> vec;
벡터<벡터<내부>> 방문;
벡터<내부> 답변;
내부 dx() = { 하나, 0, –하나, 0 };
내부 다이() = { 0, 하나, 0, –하나 };
비어 있는 친구 (내부 ㅏ, 내부 비)
{
방문(a)(b) = 하나;
내부 티 = 하나;
대기줄<쌍<내부, 내부>> 큐;
큐. 누르다 (make_pair(떨어져 있는));
~하는 동안 (!q.빈())
{
내부 엑스 = 큐앞쪽(). 첫 번째;
내부 제이 = 큐앞쪽(). 두번째;
큐팝();
// 어디서나 검색
~을 위한 (내부 나 = 0; 나 < 4; 나++)
{
내부 x_dx = 엑스 + dx(i);
내부 y_dy = 제이 + dy(I);
만약에 ((–하나 < x_dx && x_dx < 중) && // 모눈종이 내부의 첫 번째 영역
(–하나 < y_dy && y_dy < N) &&
(vec(x_dx)(y_dy) == 0) && // 2. 사각형 내부 제외
(방문(x_dx)(y_dy) == 0)) // 3. 방문하지 않음
{
큐. 누르다 (make_pair(x_dx,y_dy));
// 영역 너비
티++;
방문 (x_dx)(y_dy) = 티;
}
}
}
답변.푸시백(티);
}
내부 주로()
{
친 >> 중 >> N >> 케이;
// 모눈종이 그리기
vec. (m, 벡터<내부>(N, 0));
방문했다. 벡터<내부>(N, 0));
// vec에 사각형 그리기
내부 ABCD;
~을 위한 (내부 나 = 0; 나 < 케이; 나++)
{
친 >> ㅏ >> 비 >> 씨 >> 디;
~을 위한 (내부 제이 = 비; 제이 < 디; 제이++)
{
~을 위한 (내부 케이 = ㅏ; 케이 < 씨; 케이++)
{
vec(j)(k) = 하나;
}
}
}
~을 위한 (내부 나 = 0; 나 < 중; 나++)
{
~을 위한 (내부 제이 = 0; 제이 < N; 제이++)
{
만약에 (방문 (i) (j) == 0 && vec(i)(j) == 0)
{
bfs(i,j);
온도++;
}
}
}
쿠우트 << 온도 << “\N”;
정렬(답.시작하다(), 답변.끝());
~을 위한 (자동차& 엘: 답변) 쿠우트 << 엘레 << ” “;
돌려 주다 0;
}
|
CS |
원천 : https://www.acmicpc.net/problem/2583
#2583: 지역 찾기
첫 번째 줄에는 M, N, K가 공백을 두고 차례로 지정됩니다. M, N, K는 모두 100보다 작거나 같은 자연수이다. 두 번째 행부터 시작하는 K행에서 x, y 좌표값은 직사각형의 왼쪽 하단 모서리와
www.acmicpc.net