문제 URL :https://www.acmicpc.net/problem/16973
16973번: 직사각형 탈출
크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장
www.acmicpc.net
문제접근법 :
bfs로 접근을해서 직사각형을 움직여야 하는데 문제는 BFS를 돌때마다 직사각형 전부를
이중for문을 통해 좌우상하 움직이는 check를하면 100% 시간초과입니다. 직사각형을 한번에 움직이는 방법을 선택해야하는데 벽자체를 직사각형으로 만듭니다.
문제는 직사각형 좌상단좌표가 도착지점까지 가야하기때문에 벽자체를 우하단으로 생각하고 우하단에서 좌상단이 직사각형을 만들어 직사각형 자체를 좌상단좌표 하나만 bfs를 돌리면 답이 빠르게 나올수있습니다.
단 여기서 주의할점은 직사각형이 움직이는 거니 범위 체크를할때 빠져 좌상단 좌표가 y-h-1<n 인지 체크를해야합니다. 왜냐면 좌하단이 범위 밖을 넘어가면안되기때문에 물론 x좌표도 똑같이 마찬가지겠죠?
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n, m;
int board[1000][1000];
int sy, sx, fy, fx;
int h, w;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> board[i][j];
cin >> h >> w >> sy >> sx >> fy >> fx;
sy--, sx--, fy--, fx--;
}
struct point {
int y, x, cnt;
};
bool isrange(int y, int x) {
//좌상단좌표는 고정이고 우하단 좌표가 범위 밖으로 넘어가는지 확인
return 0 <= y && y + h - 1 < n && 0 <= x && x + w - 1 < m;
}
int bfs() {
queue<point> q;
q.push({ sy,sx,0 });
char vis[1000][1000] = { 0 };
vis[sy][sx] = 1;
while (!q.empty()) {
int y = q.front().y;
int x = q.front().x;
int cnt = q.front().cnt;
q.pop();
if (y == fy && x == fx)
return cnt;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && board[ny][nx] == 0 && vis[ny][nx] == 0) {
q.push({ ny,nx,cnt + 1 });
vis[ny][nx] = 1;
}
}
}
return -1;
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 1) {
//벽을 우하단기준으로 좌상단까지 벽을만들어줌
for (int y = i; y > i - h && y >= 0; y--) {
for (int x = j; x > j - w && x >= 0; x--) {
board[y][x] = 1;
}
}
}
}
}
cout << bfs() << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1269 대칭 차집합 (0) | 2021.06.23 |
|---|---|
| 백준 7662 이중 우선순위 큐 (0) | 2021.06.23 |
| 백준 2559 수열 (0) | 2021.06.19 |
| 백준 12930 두 가중치 (0) | 2021.06.17 |
| 백준 1080 행렬 (0) | 2021.06.17 |