[C++] 백준 1261 - 알고스팟

1261번: 알고스팟

---

풀이

BFS로 풀고 flag로 벽을 부신 횟수를 넣으면 된다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int board[101][101];
int flag[101][101];

int n, m;
int minAnswer = 1000000000;

bool InMap(int x,int y){
    if(0 <= x && x < m && 0 <= y && y < n)
    return true;
    return false;
}
void BFS(){
    queue<pair<int,pair<int,int>>> s;
    s.push(make_pair(1,make_pair(0,0)));
    
    while(!s.empty()){
        int c = s.front().first;
        int x = s.front().second.first;
        int y = s.front().second.second;
        s.pop();
        if(!InMap(x,y))
        continue;
        
        if(minAnswer <= c)
        continue;
        
        if(flag[y][x] != 0 && flag[y][x] <= c)
        continue;
        //cout << x << " " << y << " " << c << endl;   
        if(x == m-1 && y == n-1){
            minAnswer = min(c, minAnswer);
            flag[y][x] = minAnswer;
            continue;
        }
        flag[y][x] = c;
        for(int i =0;i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(!InMap(nx,ny))
            continue;
            
            if(board[y][x] == 1)
            s.push(make_pair(c+1,make_pair(nx,ny)));
            else
            s.push(make_pair(c,make_pair(nx,ny)));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    for(int y = 0;y < n; y++){
        string a;
        cin >> a;
        for(int i = 0; i < a.length(); i++){
            board[y][i] = ((int)a[i]) - ((int)'0');
        }
    }
    BFS();
    cout << minAnswer-1;
    return 0;
}