백준 2206번 C++

#include <iostream>
#include <string>
#include <queue>

using namespace std;
const int MAX = 1000;
int map[MAX][MAX];
int n, m;
int visited[MAX][MAX][2];

struct Move {
	int x, y;
};
Move mv[4] = { {1,0}, {-1,0} ,{0,1}, {0,-1} };

int bfs() {
	queue<pair<int, pair<int,int>>> q;
	q.push(make_pair(0,make_pair(0,1)));
	visited[0][0][1] = 1;

	while (!q.empty()) {
		int currenti = q.front().first;
		int currentj = q.front().second.first;
		int broke = q.front().second.second;
		q.pop();

		if (currenti == (n - 1) && currentj == (m - 1))
			return visited[currenti][currentj][broke];

		for (int k = 0; k < 4; k++) {
			int movei = currenti + mv[k].x;
			int movej = currentj + mv[k].y;

			if (movei >= 0 && movei < n && movej >= 0 && movej < m) {
				if (map[movei][movej] == 1 && broke == 1) {
					q.push(make_pair(movei, make_pair(movej, broke - 1)));
					visited[movei][movej][broke - 1] = visited[currenti][currentj][broke] + 1;
				}

				if (map[movei][movej] == 0 && visited[movei][movej][broke] == 0) {
					q.push(make_pair(movei, make_pair(movej, broke)));
					visited[movei][movej][broke] = visited[currenti][currentj][broke] + 1;
				}
			}
		}
	}
	return -1;
}

int main(void) {
	string s;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j] - '0';
		}
	}
	int answer = bfs();
	cout << answer << endl;
	return 0;
}