前提・実現したいこと
大きさがN×Mの迷路があります。迷路は通路('.')と壁'#'からできており、1ターンに隣接する上下左右4マスの通路へ移動することができます。スタート('S')からゴール('G')まで移動するのに必要な最小ターン数を求めなさい。
M, N <= 100
という問題があり、以下のように解きましたが、答えが0になってしまいます。この原因を教えていただけますか。よろしくお願いします。
該当のソースコード
c++
1#include <bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4typedef long double ld; 5const int INF = 1e8; 6 7template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } 8template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } 9 10 11int N, M; 12vector<string> maze; 13int d[110][110]; 14int dx[4] = {1, 0, -1, 0}; 15int dy[4] = {0, 1, 0, -1}; 16int sx, sy, gx, gy; 17typedef pair<int, int> P; 18 19 20int bfs(){ 21 queue<P> que; 22 23 for(int i = 0; i < N; ++i){ 24 for(int j = 0; j < M; ++j) d[i][j] = INF; 25 } 26 que.push(P(sx, sy)); 27 d[sy][sx] = 0; 28 while(que.size()){ 29 P p = que.front(); que.pop(); 30 int px = p.first, py = p.second; 31 if(px == gx && py == gy) break; 32 for(int i = 0; i < 4; ++i){ 33 int nx = px + dx[i], ny = py + dy[i]; 34 if(nx >= 0 && nx < M && ny >= 0 && ny < N && maze[ny][nx] != '#' && d[ny][nx] == INF){ 35 que.push(P(nx, ny)); 36 d[ny][nx] = d[py][px] + 1; 37 } 38 } 39 } 40 41 return d[gy][gx]; 42} 43 44 45void solve(){ 46 cout << bfs() << endl; 47} 48int main() 49{ 50 ios::sync_with_stdio(false); 51 cin.tie(0); 52 int N, M; cin >> M >> N; 53 maze.resize(N); 54 55 for(int i = 0; i < N; ++i) cin >> maze[i]; 56 for(int i = 0; i < N; ++i){ 57 for(int j = 0; j < M; ++j){ 58 if(maze[i][j] == 'S'){ 59 sx = j; sy = i; 60 } 61 if(maze[i][j] == 'G'){ 62 gx = j; gy = i; 63 } 64 } 65 } 66 solve(); 67 68}
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/01/28 13:07