[解析アルゴリズムプール]BOJ 206壁を破壊し移動する

今日解決した問題はBOJ 206壁を破壊し移動するです!
基本的にグラフィックナビゲーションの問題であり,BFSを用いたが,基本的なDFS/BFS問題では若干変形している.この部分を解決するのはコアで、メモリが超過しているため、他の位置の助けの下で解決しました、、!惜しい

BOJ 206壁を破壊し移動する

N×Mのマトリックス表現のマッピングがあります.地図では、0は移動可能な位置、1は移動不可能な壁の位置を示す.(1,1)から(N,M)の位置に移動し、最短経路に移動します.最短パスとは、地図上の最小セルを通るパスで、開始セルと終了セルが含まれます.
移動中に壁を割ったり移動したりする経路がもっと短い場合は、壁を割って移動することができます.
1つのセルで移動できるセルは上下左右に隣接するセルです.
地図を指定すると、最短パスを解くプログラムが作成されます.

にゅうしゅつりょく

私の答え

問題を読むと、典型的なDFS/BFS問題+a問題だと思います.
でもそのアルファがコアで、やっぱりその部分を解決するのに90%以上の時間と努力がかかったと思います…!
「最初は'한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면'という言葉をコードで表現するのは難しい」.「壁を通って歩くときの経路が短いとどう判断するか、、、?」私はずっと彼に付きまとっていた.
考えてみれば、いずれにしてもBFSはすべてのケースの数をカバーしているので、壁を通らない最小パス値に更新すれば解決できるので、パスが短くなるかどうかを事前に判断する必要はありません!
結果「壁を割って移動する経路がもっと短くなれば」は重要ではなく、コアは一度貫通できる!
その後,queueに入る資料型を構造体として定義する.Locationという名前の構造体が定義されており、構造体には、現在示されている地図上の위치 (row, col)と、これまでの経路移動値costと、壁を破るかどうかの値brokenが含まれている.

typedef struct location{
    pair<int, int> point;
    int cost;
    bool broken;

    location(pair<int, int> p, int c, bool b){
        this->point = p;
        this->cost = c;
        this->broken = b;
    }
}Location;

現在位置に応じて4方向からナビゲート可能であれば、Location構造体をqueueに入れながらBFSを行いコードを記述する.与えられたテスト例はよく合格し、採点中にメモリオーバーフローが発生しました.
基本的なアルゴリズム自体は問題ないはずですが、メモリが超過している場合は、構造体の問題でしょうか、問題リストには私のように構造体を定義している人にもメモリが超過していることが表示されますので、コードを改めて変更し、構造体を使用しない方法!△ここにはいくつかの制限があります.ほほほ、
しかし、いいアイデアは思いつかなかったのですが、調べてみると、3次元配列を利用している場合が多いようです!これは、アクセスチェックを行う配列を3 Dと宣言し、地図の各点をドリルスルーするときにドリルスルーがない場合を区別し、パス値で塗りつぶす方法です.3 D配列値を0に設定してアクセスすると、パス値は無条件に1より大きくなるため、アクセスの有無を同時に確認できます.
3 D配列で問題を解決して、やっと通過!!

コード#コード#

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

// BOJ 2206 벽 부수고 이동하기, BFS 심화 골드 4
using namespace std;

int MINCOST = 2147483647;

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

bool findMinWay(int N, int M, vector<vector<int>> map) {
    bool found = false;  // 반환값, 최소 경로를 찾았는지를 확인 
    vector<vector<vector<int>>> visited(N, vector<vector<int>>(M, vector<int>(2,0)));
    queue<pair<pair<int,int>, int>> q;

    q.push(make_pair(make_pair(0,0), 0));
    visited[0][0][0] = 1;
    visited[0][0][1] = 1;

    while (!q.empty()){
        pair<pair<int, int>, int> loca = q.front();
        q.pop();

        // 도착 지점이라면, 처음 도달한거면 경로를 찾았음을 저장하고, 최소 경로 값인지 확인 
        if(loca.first.first == N-1 && loca.first.second == M-1){
            if (!found) found = true;
            if (MINCOST > visited[loca.first.first][loca.first.second][loca.second]){
                MINCOST = visited[loca.first.first][loca.first.second][loca.second];
            }
            continue;
        }

        // 그 외 지점이라면 
        for (int i = 0; i < 4; ++i) {
            int row = loca.first.first + dy[i];
            int col = loca.first.second + dx[i];

            // 상하좌우 4 방면으로 확인 
            if(row>=0 && row<N && col>=0 && col<M){ // 지도 내 범위 
                if (map[row][col] == 0){  // 기존에 뚫었던 안뚫었던 갈 수 있는 칸이라면
                    if(visited[row][col][loca.second] == 0) {  // 처음 방문이면 
                        
                        // loca.second : 뚫어서 온건지, 안뚫고 온건지
                        q.push(make_pair(make_pair(row, col), loca.second));
                        visited[row][col][loca.second] = visited[loca.first.first][loca.first.second][loca.second] + 1;
                    }
                }else{  // 벽을 만나면 
                    if (loca.second == 0){  // 뚫지 않고 온거면 
                        
                        // 이제 뚫는 거니까 visited 3번째 index = 1 
                        visited[row][col][1] = visited[loca.first.first][loca.first.second][loca.second] + 1;
                        q.push(make_pair(make_pair(row, col), 1));
                    }
                }
            }
        }
    }

    return found;
}

int main() {
    int N, M;
    cin>>N>>M;

    vector<vector<int>> map(N, vector<int>(M, 0));

    string row;
    for (int i = 0; i < N; ++i) {
        cin>>row;
        for (int j = 0; j < M; ++j) {
            if (row[j] == '1'){
                map[i][j] = 1;
            }
        }
    }

    if (findMinWay(N, M, map)){
        cout<<MINCOST<<'\n';
    }else{
        cout<<-1<<'\n';
    }

    return 0;
}

少し難易度が上がっただけで、なかなか…!🥲
もっと解こう!!がんばって!
[BOJ 206]壁を破って移動(Python)