Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 충돌 알고리즘
- C++
- AABB
- PS
- SOH
- 리눅스
- 알고리즘
- 외적
- Vector
- 백준
- Doubly Connected Edge List
- 보로노이다이어그램
- dp
- 우분투
- C
- 벡터
- uclidean algorithm
- 다이나믹 프로그래밍
- ubuntu
- c#
- Unity
- 문제풀이
- linux
- 유니티
- Graham Scan
- 내적
- Expanding Polytope Algorithm
- 수학
- 분할축 이론
- GJK
Archives
- Today
- Total
마이 플밍 블로그
[C++] 백준 14442 - 벽 부수고 이동하기 2 본문
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
풀이
이전에 했던 1600 말이 되고픈 원숭이랑 비슷하게 풀었다.
남은 벽부수기 횟수에따른 flag를 배열을 만들고 남은거리를 저장했다.
코드
#include <bits/stdc++.h>
using namespace std;
int board[1001][1001];
int flag[1001][1001][11];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int w,h,k;
int answer = 10000000;
bool InMap(int x,int y){
if(0 <= x && x < w && 0<= y && y < h)
return true;
return false;
}
void bfs(){
// x y 벽횟수 이동거리
queue<pair<pair<int,int>,pair<int,int>>> q;
q.push(make_pair(make_pair(0,0), make_pair(k,1)));
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int c = q.front().second.first;
int l = q.front().second.second;
q.pop();
if(!InMap(x,y))
continue;
if(board[y][x] == 1 && c <= 0){
continue;
}
if(board[y][x] == 1 && c > 0){
c--;
}
if(flag[y][x][c] != 0 && flag[y][x][c] <= l)
continue;
if(answer <= l)
continue;
if(x == w-1 && y == h-1){
answer = min(answer, l);
flag[y][x][c] = answer;
continue;
}
flag[y][x][c] = l;
for(int i = 0; i < 4; i++){
int nx = dx[i] + x;
int ny = dy[i] + y;
q.push(make_pair(make_pair(nx,ny), make_pair(c,l+1)));
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> h >> w >> k;
string s;
for(int y = 0; y < h; y++){
cin >> s;
for(int i =0; i < s.length(); i++){
board[y][i] = ((int)s[i] - (int)'0');
}
}
bfs();
if(answer != 10000000)
cout << answer;
else{
cout << -1;
}
return 0;
}
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 11779 - 최소비용 구하기 2 (1) | 2023.10.08 |
---|---|
[C++] 백준 2234 - 성곽 (1) | 2023.10.07 |
[C++] 백준 1600 - 말이 되고픈 원숭이 (1) | 2023.10.06 |
[C++] 백준 2146 - 다리 만들기 (0) | 2023.10.01 |
[C++] 백준 5567 - 결혼식 (0) | 2023.02.26 |