(2206) 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

단계별로 풀어보기

27단계(그래프와 순회) 15번째

 

 

 

벽을 하나 부술 수 있으므로, 미로 내 좌표 뿐만 아니라 벽을 부쉈는지 여부 또한 상태로 관리해야 한다.

다음 탐색 지점이 벽이여도 현재 상태에서 벽을 부순 적이 없다면 벽을 부순 상태로 다음 지점을 탐색할 수 있다.

탐색이 모두 끝난 뒤에는 도착 지점의 모든 벽 여부 상태를 탐색하여 그 중 최솟값이 답이 된다.

 

 

 

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

struct Cord{
  int x;
  int y;
  int w;
  
  Cord(int x0, int y0, int w0): x(x0), y(y0), w(w0) {};
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector v(n, vector<bool> (m));
  vector dist(n, vector (m, vector<int> (2, -1)));
  
  for(int i=0;i<n;i++){
    string s;
    
    cin >> s;
    
    for(int j=0;j<m;j++)  v[i][j]= s[j]=='0';
  }
  
  queue<Cord> q;
  
  q.push(Cord(0,0,0));
  dist[0][0][0]= 1;
  
  while(!q.empty()){
    int nowx= q.front().x;
    int nowy= q.front().y;
    int w= q.front().w;
    q.pop();
    
    for(int i=0;i<4;i++){
      int nextx= nowx+"0121"[i]-'1';
      int nexty= nowy+"1012"[i]-'1';
      
      if(nextx<0 || nextx>n-1 || nexty<0 || nexty>m-1)  continue;
      if(dist[nextx][nexty][w]!=-1)  continue;
      
      if(v[nextx][nexty]){
        dist[nextx][nexty][w]= dist[nowx][nowy][w]+1;
        q.push(Cord(nextx,nexty,w));
      }else{
        if(w==1)  continue;
        
        dist[nextx][nexty][w+1]= dist[nowx][nowy][w]+1;
        q.push(Cord(nextx,nexty,w+1));
      }
    }
  }
  
  int ans= 1000001;
  for(int i=0;i<=1;i++){
    if(dist[n-1][m-1][i]!=-1)  ans= min(ans, dist[n-1][m-1][i]);
  }
  
  cout << (ans==1000001 ? -1 : ans);
  
  return 0;
}