[BOJ] 16928. 蛇と梯子ゲーム-c++

1440 ワード
BFS boj テキストリンク
https://www.acmicpc.net/problem/16928

100コマに達するにはサイコロを投げる回数の最高値が必要です.
=>(queue)を使用したBFS
C++プール
int mve[102]=ヘビ/はしごに移動した情報の一部を保存(デフォルト)
int N,M;
int mve[102];
int visited[102];

int main()
{
  cin>>N>>M;
  for(int i=1;i<101;i++){
      mve[i]=i;
      visited[i]=-1;
  }
  for(int i=0;i<N+M;i++){
      int x,y;
      cin>>x>>y;
      mve[x]=y;
  }
  
  queue<int> q;
  q.push(1);
  visited[1]=0;
  while(!q.empty()){
      int cur = q.front();
      q.pop();
      for(int i=1;i<=6;i++){
          int nxt = cur +i;
          if(nxt>100) continue;
          nxt= mve[nxt];//사다리 or 뱀 이동 
          
          if(visited[nxt]==-1){//방문한적 없는 경우 
              visited[nxt] = visited[cur]+1;
              q.push(nxt);
          }
      }
  }
  cout<<visited[100];
      
}
scroll
Go - Chancho - 4によるダイナモ