(2178) 미로 탐색

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

단계별로 풀어보기

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

 

 

 

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

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<int> (m, -1));
  
  for(int i=0;i<n;i++){
    string s;
    
    cin >> s;
    
    for(int j=0;j<m;j++)  v[i][j]= s[j]=='1';
  }
  
  queue<int> q;
  
  q.push(0);
  dist[0][0]= 1;
  
  while(!q.empty()){
    int nowx= q.front()/m;
    int nowy= q.front()%m;
    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(!v[nextx][nexty])  continue;
      if(dist[nextx][nexty]!=-1)  continue;
      
      dist[nextx][nexty]= dist[nowx][nowy]+1;
      q.push(nextx*m+nexty);
    }
  }
  
  cout << dist[n-1][m-1];
  
  return 0;
}