알고스팟

*우선순위큐를 사용해서 더 적게 벽을 뿌순 순서대로 정렬하여 큐에서 꺼낸다. 

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
 
#define INF 987654321
using namespace std;
int n, m, ans = INF;
int map[101][101];
 
typedef pair<int, int> pp;
typedef pair<int ,pp> ipp;
bool visited[101][101];
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
 
bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y]) return false;
    return true;
}
void bfs(int x, int y) {
    priority_queue<ipp, vector<ipp>, greater<ipp> > q;
    q.push(ipp(0, pp(x, y)));
 
    visited[x][y] = true;
 
    while(!q.empty()) {
        int size = q.size();
 
        while(size--) {
            int x = q.top().second.first;
            int y = q.top().second.second;
            int cnt = q.top().first;
            q.pop();
 
            if (x == n-1 && y == m-1) {
                ans = min(ans, cnt);
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (check(nx, ny)) {
                    visited[nx][ny] = true;
                    if (map[nx][ny])
                        q.push(ipp(cnt+1, pp(nx, ny)));
                    else q.push(ipp(cnt, pp(nx, ny)));
                }
            }
            
        }
    }
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++) {
            map[i][j] = s[j] - '0';
        }
    }
 
    bfs(0,0);
 
    cout << ans << '\n';
 
    return 0;
}