[C++]BOJ 2206 - 벽 부수고 이동하기

bfs로 갈 수 있는 경로를 탐색하면서 벽을 만났을 때 벽을 부순적이 없다면 벽을 부수고 이동하고 벽을 부순적이 있다면 지나간다.
벽을 부순적이 있는가 여부를 담을 큐 하나를 추가로 만들어주고 x, y와 함께 담아서 매칭시킨다.
처음에는 방문처리를 위한 v배열을 2차원으로 구성했는데 오답으로 처리됐다.
이유를 생각해보니 같은 위치에 있더라도 벽을 부순적이 있는 경로를 지나쳤거나 부순적이 없는 경로를 지나쳤거나 두 가지 경우가 있기 때문에 몇가지 경우의 수가 누락된다.
따라서 같은 위치라도 부순적이 있을 때, 없을 때도 고려해서 방문처리를 해 주어야 한다.

#include <iostream>
#include <queue>
using namespace std;
int n, m, cx, cy, cd, xx, yy, arr[1002][1002], v[1002][1002][2], dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}, mn, mx;
queue<int> qx, qy, qd;
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%1d", &arr[i][j]);
	qx.push(1), qy.push(1), qd.push(0); v[1][1][0] = 1;
	while(!qx.empty()) {
		cx = qx.front(); qx.pop();
		cy = qy.front(); qy.pop();
		cd = qd.front(); qd.pop();
		for(int i = 0; i < 4; i++) {
			xx = cx + dx[i]; yy = cy + dy[i];
			if(xx > m || yy > n || xx < 1 || yy < 1 || v[yy][xx][cd]) continue;
			if(arr[yy][xx]) {
				if(cd) continue;
				v[yy][xx][1] = v[cy][cx][0] + 1;
				qx.push(xx), qy.push(yy), qd.push(1);
				continue;
			}
			v[yy][xx][cd] = v[cy][cx][cd] + 1;
			qx.push(xx), qy.push(yy), qd.push(cd);
		}
	}
	mn = min(v[n][m][0], v[n][m][1]); mx = max(v[n][m][0], v[n][m][1]);
	if(mn) cout << mn;
	else if(mx) cout << mx;
	else cout << "-1";
}