(문제에서는 1이 벽으로 설정되었는데, 해당 코드에서는 map에 저장된 값이 0일 때를 벽으로 설정하였습니다)
#include <stdio.h>
#include <queue>
using namespace std;
bool map[1001][1001], visited[2][1001][1001];
int Min[2][1001][1001];
auto BFS(int N, int M) {
int d[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int x, y, nx, ny;
bool wall;
queue <pair<pair<int, int>, bool>> Q;
// init
Q.push({ {0,0},0 });
visited[0][0][0] = visited[1][0][0] = Min[0][0][0] = Min[1][0][0] = true;
// BFS
while (!Q.empty()) {
// (x,y) : 현재 위치, wall : 벽을 부술 수 있는 지 (있으면 0, 이미 부셨으면 1)
x = Q.front().first.first, y = Q.front().first.second, wall = Q.front().second;
Q.pop();
for (int i = 0; i < 4; i++) {
nx = x + d[i][0], ny = y + d[i][1];
if (nx < 0 || nx > N || ny < 0 || ny > M) continue;
// 벽일 때
if (!map[nx][ny]) {
// 벽을 부술 수 있고, 방문하지 않았을 경우
if (!wall && !visited[1][nx][ny]) {
visited[1][nx][ny] = true;
Min[1][nx][ny] = Min[wall][x][y] + 1;
Q.push({ {nx,ny},true });
}
}
// 벽이 아닐 때
else {
// 방문 여부만 판단
if (!visited[wall][nx][ny]) {
visited[wall][nx][ny] = true;
Min[wall][nx][ny] = Min[wall][x][y] + 1;
Q.push({ {nx,ny},wall });
}
}
}
}
// print
if (!visited[0][N][M]) {
if (!visited[1][N][M]) return -1;
else return Min[1][N][M];
}
else {
if (!visited[1][N][M]) return Min[0][N][M];
else return Min[0][N][M] < Min[1][N][M] ? Min[0][N][M] : Min[1][N][M];
}
}
int main() {
int N, M;
char s[1003];
// input
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%s", s);
for (int j = 0; j < M; j++) {
if (s[j] == '0') map[i][j] = true;
}
}
printf("%d", BFS(N - 1, M - 1));
return 0;
}