17836 공주님을 구해라!
2019. 11. 13. 01:07ㆍ알고리즘/백준
bfs문제로 검을 얻었을 때와 얻지 않았을 때의 최소거리를 구분해줘서 마지막 답에서 비교해서 최소값만 구하면 된다
문제: https://www.acmicpc.net/problem/17836
깃허브주소: https://github.com/surinoel/boj/blob/master/17836.cpp
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <tuple> | |
#include <queue> | |
#include <cstring> | |
#include <iostream> | |
using namespace std; | |
int mat[100][100]; | |
int dist[100][100][2]; | |
int dx[4] = { 1, -1, 0, 0 }; | |
int dy[4] = { 0, 0, 1, -1 }; | |
int main(void) { | |
ios_base::sync_with_stdio(false); | |
cin.tie(nullptr); | |
int n, m, t; | |
cin >> n >> m >> t; | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
cin >> mat[i][j]; | |
} | |
} | |
memset(dist, -1, sizeof(dist)); | |
queue<tuple<int, int, int>> q; | |
q.push(make_tuple(0, 0, 0)); | |
dist[0][0][0] = 0; | |
while (!q.empty()) { | |
int x, y, z; | |
tie(x, y, z) = q.front(); | |
q.pop(); | |
for (int k = 0; k < 4; k++) { | |
int tx = x + dx[k]; | |
int ty = y + dy[k]; | |
if (tx < 0 || ty < 0 || tx > n - 1 || ty > m - 1) continue; | |
if (z == 0) { | |
if (mat[tx][ty] == 0 && dist[tx][ty][z] == -1) { | |
dist[tx][ty][z] = dist[x][y][z] + 1; | |
q.push(make_tuple(tx, ty, z)); | |
} | |
else if (mat[tx][ty] == 2 && dist[tx][ty][z] == -1) { | |
dist[tx][ty][1] = dist[x][y][z] + 1; | |
q.push(make_tuple(tx, ty, 1)); | |
} | |
} | |
else { | |
if ((mat[tx][ty] == 0 || mat[tx][ty] == 1) && dist[tx][ty][z] == -1) { | |
dist[tx][ty][z] = dist[x][y][z] + 1; | |
q.push(make_tuple(tx, ty, z)); | |
} | |
} | |
} | |
} | |
int ans = -1; | |
if (ans == -1 || ans > dist[n - 1][m - 1][0]) { | |
ans = dist[n - 1][m - 1][0]; | |
} | |
if (ans == -1 || ans > dist[n - 1][m - 1][1]) { | |
ans = dist[n - 1][m - 1][1]; | |
} | |
if (ans >= 0 && ans <= t) { | |
cout << ans << '\n'; | |
} | |
else { | |
cout << "Fail\n"; | |
} | |
return 0; | |
} |
'알고리즘 > 백준' 카테고리의 다른 글
스택 연결리스트로 구현하기 (0) | 2019.11.15 |
---|---|
17837 새로운 게임 2 (0) | 2019.11.14 |
[삼성] 17825 주사위 윷놀이 (1) | 2019.11.05 |
2042 구간 합 구하기 (0) | 2019.10.30 |
[삼성] 17780 새로운 게임 (0) | 2019.10.28 |