BOJ : 1261 알고스팟

문제 : https://www.acmicpc.net/problem/1261

일반적인 미로찾기에서 아주 사알짝 업그레이드 된 문제.

1. 벽 어느 벽을 부쉈냐에 따라 이동경로가 달라질 수 있기 때문에 주의하도록 하자.

2. 또 최소 이동거리가 아닌 부순 벽의 개수가 최소가 되어야 하기 때문에 모든 이동경로를 비교해야 한다.

비슷한 문제

2206 벽 부수고 이동하기 / 해설

14442 벽 부수고 이동하기 2 /  해설

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

struct Pos{
public:
    int r,c,crash;
    Pos(){}
    Pos(int _r,int _c,int _crash) : r(_r), c(_c), crash(_crash) {}
};
int N,M,ans=987654321;
char map[102][102];
bool visited[102][102][1003];
int pr[4] = {1,-1,0,0};
int pc[4] = {0,0,1,-1};
queue<Pos> q;

int main(){
    scanf("%d%d",&M,&N);
    for(int i=0;i<N;i++)
        scanf("%s",map[i]);
    
    q.push(Pos(0,0,0));
    visited[0][0][0]=1;
    
    while(!q.empty()){
        int r = q.front().r , c = q.front().c, cnt = q.front().crash;
        q.pop();
        
        //printf("%d %d %d\n",r,c,cnt);
        if(r==N-1 && c==M-1){
            if(ans > cnt) ans = cnt;
        }
        for(int i=0;i<4;i++){
            int nr = r+pr[i], nc = c+pc[i], nCnt=cnt;
            if(nr<0 || nc<0 || nr>=N || nc>=M) continue;
            if(visited[nr][nc][nCnt]) continue;
            if(map[nr][nc]=='1') {
                nCnt += 1;
                if(visited[nr][nc][nCnt]) continue;
            }
            visited[nr][nc][nCnt]=1;
            q.push(Pos(nr,nc,nCnt));
        }
    }
    printf("%d\n",ans);
}                                                    Colored by Color Scripter