문제:
2665번: 미로만들기
첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.
www.acmicpc.net
코드:
벽을 부쉈다고해서 map에 반영시킬 필요 없음!
/* 1. 벽을 부쉈다고 mz에 반영시킬 필요 없음 */
/* 2. 벽을 부술 수 있는 경우의 수는 src, dst간 최단 거리인 50 * 2 - 2 */
#include <iostream>
#include <queue>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
bool mz[50][50];
bool vst[50][50][98]; /* 2 */
struct qnode {
int r, c, d;
};
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N; cin >> N;
f(r, N) f(c, N) {
char ch; cin >> ch;
mz[r][c] = ch - '0';
}
vst[0][0][0] = 1;
queue<qnode> q;
q.push({ 0, 0, 0 });
int ans = 2500;
while (!q.empty()) {
qnode pt = q.front(); q.pop();
if (pt.d < ans) {
if (pt.r == N - 1 && pt.c == N - 1)
ans = pt.d;
}
else
continue;
for (int d = 0; d < 4; ++d) {
int nr = pt.r + dr[d], nc = pt.c + dc[d];
if (nr < 0 || N <= nr || nc < 0 || N <= nc) continue;
if (mz[nr][nc]) { // 안 깨기
if (vst[nr][nc][pt.d]) continue;
vst[nr][nc][pt.d] = 1;
q.push({ nr, nc, pt.d });
}
else { // 깨기
if (vst[nr][nc][pt.d + 1]) continue;
vst[nr][nc][pt.d + 1] = 1;
q.push({ nr, nc, pt.d + 1 });
}
}
}
cout << ans;
return 0;
}