전쟁 - 진군

BOJ 전쟁 - 진군 1261

SOL)

PQ를 이용하여 가장 적게 장애물을 없앤 녀석 부터 계산을 하고
가장 먼저 목표지점에 도달한 녀석의 장애물을 없앤 값이 답

DP로 풀수도 있고, 그때 그때 최선의 선택을 하는게 그리드 같고 그래프 같기도 하고 ㅎㅎ

[-] Collapse

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

#define Y first
#define X second

int board[101][101];
int visit[101][101];

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };

int main(){
    int n, m;  scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        scanf("%1d", &board[i][j]);

    priority_queue<pair<int, pair<int, int> > > pq;
    pq.push(make_pair(0, make_pair(1,1)));
    visit[1][1] = true;
    while (true){
        int val = -pq.top().first;
        int y = pq.top().second.Y;
        int x = pq.top().second.X;
        pq.pop();

        if (y == n && x == m){ printf("%d", val); break; }

        for (int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;
            pq.push(make_pair(-(val + board[ny][nx]), make_pair(ny, nx)));
            visit[ny][nx] = true;
        }
    }
}