2178 미로탐색

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>

using namespace std;

int N,M,answer;

int Check[101][101]; // 시작점으로부터의 거리 표시
int Map[101][101];
bool Vist[101][101];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };

void Input()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		string row;
		cin >> row;
		for (int j = 0; j < M; j++)
		{
			int data = 0;
			if (row[j] == '1') data = 1;
			Map[i][j] = data;
		}
	}
}

void Bfs(int row,int cal)
{
	Vist[row][cal] = true;
	queue<pair<int,int>> q;
	q.push(make_pair(row, cal));
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nextX = x + dr[i];
			int nextY = y + dc[i];
			if (0 > nextX || nextX > N || nextY < 0 || nextY > M) continue;

			if (Map[nextX][nextY] == 1 && Vist[nextX][nextY] == false)
			{
				Check[nextX][nextY] = Check[x][y] + 1;
				Vist[nextX][nextY] = true;
				q.push(make_pair(nextX, nextY));
			}
		}
	}
}
//void printf() {
//	for (int i = 0; i < N; i++)
//	{
//		for (int j = 0; j < M; j++)
//		{
//			cout << Map[i][j] << " ";
//		}
//		cout << endl;
//	}
//}
void Solution() {
	Bfs(0,0);
	answer = Check[N-1][M-1] + 1;
}
void Solve() {
	Input();
	Solution();

	cout << answer << '\n';
}
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();
}