[BOJ] 1261 : 알고스팟

#include <cstdio>
#include <queue>
using namespace std;

const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
const int n_ = 100 + 5;

struct edg { 
	int x, y, w;
	bool operator <(edg A)const { return w > A.w; }
};

int main() {
	int n, m, chk[n_][n_] = {};
	char a[n_][n_];
	priority_queue<edg> pq;

	scanf("%d %d\n", &m, &n);
	for (int i = 0; i < n; i++) scanf("%s", a[i]);

	pq.push({ 0,0,0 });
	while (!pq.empty()) {
		edg top = pq.top(); pq.pop();
		if (top.x == n - 1 && top.y == m - 1) {
			return !printf("%d", top.w);
		}
		chk[top.x][top.y] = 1;
		for (int i = 0; i < 4; i++) {
			int nx = top.x + dx[i], ny = top.y + dy[i];
			int nw = top.w + (a[nx][ny] == '1' ? 1 : 0);
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || chk[nx][ny]) continue;
			pq.push({ nx,ny,nw });
		}
	}

	return 0;
}