[실1] 2178 - 미로탐색

특이사항) 좌표 (1,1)부터 (y,x)까지 이동하라는데 (1,1)부터 시작 시 로직이 복잡해지므로 (0,0)부터 시작

 

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

using namespace std;

#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0);
#define y first
#define x second

using IntPair = pair<int, int>;

IntPair dir[]
{
	{1, 0},	  // 상
	{-1, 0},  // 하
	{0, -1},  // 좌
	{ 0, 1 },  // 우
};

vector<vector<int>> map, dist;
queue<IntPair> q;
int y, x, cnt;

void Bfs()
{
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		//cout << cur.y << ' ' << cur.x << endl;

		for (int i = 0; i < 4; i++)
		{
			int ny = cur.y + dir[i].y, nx = cur.x + dir[i].x;

			if (ny >= y ||
				ny < 0 ||
				nx >= x ||
				nx < 0)
				continue;

			// 방문 가능
			if (dist[ny][nx] == 0 &&
				map[ny][nx])
			{
				//map[ny][nx] = 0;
				q.push({ ny,nx });
				dist[ny][nx] = dist[cur.y][cur.x] + 1;
			}
		}
	}
}

int main()
{
	FAST_IO();
	cin >> y >> x;
	map.resize(y);
	dist.resize(y, vector<int>(x));
	dist[0][0] = 1;
	q.push({ 0, 0 });

	for (int _y = 0; _y < y; _y++)
	{
		string str;
		cin >> str;

		for (int i = 0; i < str.size(); i++)
			map[_y].push_back(str[i] - '0');
	}
	Bfs();
	cout << dist[y - 1][x - 1];
	return 0;
}