[アルゴリズム解析]プログラマーゲームマップ最短距離

筋肉感覚を軽く少しずつ身につける.大変ですね.
今日はレベル2の難易度で簡単な解答がプログラマーゲームマップ最短距離です!

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

RORゲームは2チームに分かれて行い、先に相手陣営を破壊すれば勝つゲームです.そのため、各チームはできるだけ早く相手陣営に到着したほうがいい.
これからはチームのメンバーになってゲームをします.以下に、5×5サイズのマップで、キャラクタが(行:1、列:1)、相手陣営が(行:5、列:5)の位置にある例を示します.

上図では、黒い部分は壁に塞がれて歩けない道で、白い部分は歩ける道です.キャラクターが移動するときは東、西、南、北に1コマずつ移動し、ゲームマップから離れることはできません.
次の例では、キャラクタが相手の陣営に向かう2つの方法を示します.

1つ目の方法は、11の格を経て相手陣営に到着することです.

第2の方法は15格子を経て相手陣営に到着する.

上記の例では、第1の方法ほど相手陣営に早く到達する方法はないので、相手陣営に向かう最も速い方法である.
相手が自分の陣営の周りに壁を立てたら、相手の陣営に届かないかもしれない.たとえば、次の場合、キャラクタは相手の陣営に到達できません.

ゲームマップのステータスマップをパラメータとして与える場合は、solution関数を完了し、キャラクタを相手陣営が通過する必要がある格子数の最大値に戻します.でも相手陣営に届かない時は-1に戻ってください
[制限]

地図は、n x mサイズのゲーム地図状態を含む2次元配列であり、nとmはそれぞれ1または100以下の自然数である.

nとmは同じでも異なっていてもよいが、nとmがともに1である場合、入力は与えられない.

マッピングは0と1のみで構成され、0は壁のある位置を表し、1は壁のない位置を表す.

最初のキャラクターはゲームマップの左上隅(1,1)の位置にあり、相手陣営はゲームマップの右下隅(n,m)の位置にある.

にゅうしゅつりょく

mapsanswer[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]11[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]-1

私の答え

レベル2の問題なので、簡単なBFSを適用して解決できると思います.特に制限事項や条件はないので、アクセス処理、移動距離をよくチェックすればよい.
出発位置(0,0)から目標地点(n,m)までは、BFSで移動しながら移動する距離disとともにqueueに格納されており、取り出し時に確認できる.
重複アクセスを回避するために、n×mサイズのアクセス処理配列visitedを宣言するとともに、queueにプッシュされる前に、重複アクセスが発生しないようにアクセス処理を行わなければならないことが重要である.queueから取り出したポイントがターゲットポイントなら、最小距離であることを確認し、正解を更新すれば解決!

コード#コード#

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[4] = {0,1,0,-1};
int dy[4] = {-1, 0,1,0};

struct point {
    int r;
    int c;
    int dis;

    point(int row, int col, int distance){
        r = row;
        c = col;
        dis = distance;
    }
};

int solution(vector<vector<int>> maps){
    int answer = -1;
    int n = maps.size(), m = maps[0].size();

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<point> q;
    q.push(point(0,0,1));

    while (!q.empty()){
        point cur = q.front();
        q.pop();

        if (cur.r == n-1 && cur.c == m-1){
            if(answer==-1) answer = cur.dis;
            else {
                if (answer>cur.dis) answer = cur.dis;
            }
            continue;
        }

        for (int i = 0; i < 4; ++i) {
            int nr = cur.r + dy[i];
            int nc = cur.c + dx[i];

            if (nr<0||nr>=n||nc<0||nc>=m) continue;
            if (maps[nr][nc] == 0) continue;

            if (!visited[nr][nc]) {
                visited[nr][nc] = true;
                q.push(point(nr, nc, cur.dis+1));
            }
        }
    }

    return answer;
}