백준 소스코드 [C++] 2206 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

백준 소스코드 [C++] 2206 벽 부수고 이동하기

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

#define dot first
#define flag second
int n, m;
int arr[1002][1002];
int dist[1002][1002][2];
struct dots {
	int y, x, chk,cost;
};

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
void bfs() {
	queue<dots> q;
	q.push({ 1,1,0,1 });
	while (q.empty() != true) {
		dots n = q.front();
		q.pop();
		for (int i = 0;i < 4;i++) {
			if (arr[n.y + dy[i]][n.x + dx[i]] == 1) {
				if (n.chk == 0 && n.cost + 1 < dist[n.y + dy[i]][n.x + dx[i]][1]) {
					dist[n.y + dy[i]][n.x + dx[i]][1] = n.cost + 1;
					q.push({ n.y + dy[i],n.x + dx[i],1,n.cost + 1 });
				}
			}
			else if (arr[n.y + dy[i]][n.x + dx[i]] == 0) {
				if (n.cost + 1 < dist[n.y + dy[i]][n.x + dx[i]][n.chk]) {
					dist[n.y + dy[i]][n.x + dx[i]][n.chk] = n.cost + 1;
					q.push({ n.y + dy[i],n.x + dx[i],n.chk,n.cost + 1 });
				}
			}
		}
	}
	if (min(dist[n][m][0], dist[n][m][1]) < INT_MAX) cout << min(dist[n][m][0], dist[n][m][1]);
	else cout << "-1";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	string s;
	for (int i = 0;i <= n + 1;i++)
		for (int j = 0;j <= m + 1;j++)
			arr[i][j] = 2;

	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			dist[i][j][0] = dist[i][j][1] = INT_MAX;
	dist[1][1][0] = dist[1][1][1] = 1;

	for (int i = 1;i <= n;i++) {
		cin >> s;
		for (int j = 1;j <= m;j++)
			arr[i][j] = s[j - 1] - '0';
	}

	bfs();
	return 0;
}