문제 URL : https://www.acmicpc.net/problem/17267
17267번: 상남자
CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하
www.acmicpc.net
문제 접근법 :
아래 사진과 같은 조건일때
위아래로는 벽을 만나거나 board범위 끝까지 도달할수있습니다.
하지만 왼쪽과 오른쪽은 정해진 칸수만큼만 가서 모든 경우의수를 찾아 밟을수있는 모든땅을 알아내는겁니다.
방법은 간단합니다. 최대한 많은 땅을 밟기위해 할수있는것은 Bfs를 이용하여 위아래로 모든땅을 먼저밟고 난후
왼쪽과 오른쪽을 나중에 밟게하는것이 최선입니다
그래야 아래와같은 결과물이 나올수있습니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
int n, m;
vvi board, check;
int sy, sx;
int L, R;
int dy[4] = {-1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int decl[4] = { 0,0,-1,0 };
int decr[4] = { 0,0,0,-1 };
void input() {
cin >> n >> m;
cin >> L >> R;
board=vvi(n, vi(m));
char c;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
if (c == '1')
board[i][j] = 1;
else if (c == '2') {
sy = i, sx = j;
}
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
void straight(int y,int x,int dir,int l,int r, queue<tuple<int, int, int, int>> &q) {
if (!isrange(y, x))return;
if (board[y][x]||check[y][x])return;
check[y][x] = 1;
straight(y + dy[dir], x + dx[dir], dir, l, r, q);
q.push({ y,x,l,r });
}
int bfs() {
queue<tuple<int,int,int,int>> q;
check = vvi(n, vi(m));
q.push({ sy,sx,L,R });
check[sy][sx] = 1;
while (!q.empty()) {
int qsize = q.size();
int y, x, l, r;
while (qsize--) {
tie(y, x, l, r) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
if (i < 2) {
straight(y+dy[i], x+dx[i], i,l, r,q);
}
else {
int ny, nx, nl, nr;
tie(ny, nx, nl, nr) = make_tuple(y + dy[i], x + dx[i], l + decl[i], r + decr[i]);
if (isrange(ny, nx) && !check[ny][nx] && !board[ny][nx]) {
if ((decl[i] == -1 && nl >= 0) || (decr[i] == -1 && nr >= 0)) {
q.push({ ny,nx,nl,nr });
check[ny][nx] = 1;
}
}
}
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res += check[i][j];
}
}
return res;
}
void solve() {
cout << bfs() << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점
어떤질문이든 댓글은 언제나 환영입니다. 공감 눌러주실꺼죠?
'백준' 카테고리의 다른 글
| 백준 2842 집배원 한상덕 (0) | 2021.08.31 |
|---|---|
| 백준 2505 두 번 뒤집기 (0) | 2021.08.26 |
| 백준 1942 디지털 시계 (0) | 2021.08.23 |
| 백준 8595 히든 넘버 (0) | 2021.08.22 |
| 백준 22351 수학은 체육과목 입니다3 (0) | 2021.08.22 |
