[BOJ] 16973 직사각형 탈출

Time Lapse :18min 36sec

16973.cpp

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
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <stdlib.h>
using namespace std;
int n, m, h, w, sy, sx, ey, ex;
int map[1000][1000];
int v[1000][1000];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
void changeMap() {
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j) {
if(map[i][j] == 1) {
int mini = min(i+1, n), minj = min(j+1, m);
for(int ni = max(i - h + 1, 0); ni <mini; ++ni)
for(int nj = max(j - w + 1,0); nj <minj; ++nj) {
if(!map[ni][nj])
map[ni][nj] = 2;
}
}
}
}
int main(void) {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
scanf("%d",&map[i][j]);
memset(v, -1, sizeof(v));
scanf("%d %d %d %d %d %d", &h, &w, &sy, &sx, &ey, &ex);
--sy; --sx; --ey; --ex;
changeMap();
queue<pair<int, int>> q;
q.push(make_pair(sy, sx));
v[sy][sx] = 0;
while(!q.empty()) {
pair<int, int> p = q.front();
q.pop();
for(int i = 0; i < 4; ++i) {
int nx = p.second + dx[i];
int ny = p.first + dy[i];
if(0<= nx && nx <= m - w && 0 <= ny && ny <= n - h && !map[ny][nx] && v[ny][nx] == -1) {
v[ny][nx] = v[p.first][p.second] + 1;
q.push(make_pair(ny, nx));
if(ny == ey && nx == ex) {
printf("%d",v[ey][ex]);
exit(0);
}
}
}
}
printf("%d",v[ey][ex]);
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/08/26/PS/BOJ/16973/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.