[プログラマー]ゲームマップ最短距離

11899 ワード
level2 supin2 プログラマ cpp テキストリンク
回答日:2021年-08-12

質問する


質問リンク:https://programmers.co.kr/learn/courses/30/lessons/1844

アクセスと解析


これは典型的なBFS,DFS問題である.
BFSを使用して出発点から到着点まで、壁の有無、アクセスの有無、範囲を確認して移動します.
到着時刻に最低時間の値を返却しました.

コード#コード#

#include <vector>
#include <queue>

using namespace std;

struct Point {
    int y, x, cnt;
};

#define INF 987654321

int solution(vector<vector<int> > maps)
{
    int answer = INF;
    int rowSize = maps.size(), colSize = maps.front().size();
    int dir[4][2] = {{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};
    bool visited[101][101] = { false };
    
    queue<Point> q;
    q.push({ 0, 0, 1 });
    visited[0][0] = true;
    
    while (!q.empty()) {
        Point now = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nextY = now.y + dir[i][0], nextX = now.x + dir[i][1];
            
            if (nextY == rowSize - 1 && nextX == colSize - 1) {
                answer = min(answer, now.cnt + 1);
                continue;
            }
            if (nextY < 0 || nextY >= rowSize || nextX < 0 || nextX >= colSize) {
                continue;
            }
            if (visited[nextY][nextX] == true || maps[nextY][nextX] == 0) {
                continue;
            }
            q.push({ nextY, nextX, now.cnt + 1 });
            visited[nextY][nextX] = true;
        }
    }
    
    if (answer == INF) {
        return -1;
    } else {
        return answer;
    }
}

結果



フィードバック


BFSの実施に慣れていると思います.
マルチスレッドプログラミング学習9(同時ツールクラス).
position