https://www.acmicpc.net/problem/2178
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int N, M;
int maze[101][101] = { 0, };
int direct[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
queue<pair<int, int>> q;
void BFS()
{
int nx, ny;
pair<int, int> cur;
q.push({ 0, 0 });
while (!q.empty())
{
cur = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
nx = cur.first + direct[i][0]; // j
ny = cur.second + direct[i][1]; // i
if (nx >= 0 && nx < M && ny >= 0 && ny < N && maze[ny][nx] == 1)
{
q.push({ nx, ny });
maze[ny][nx] = maze[cur.second][cur.first] + 1;
}
}
}
}
int main(void)
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
for (int j = 0; j < M; j++)
{
maze[i][j] = str[j] - '0';
}
}
BFS();
cout << maze[N - 1][M - 1];
return 0;
}