[Baekjoon]206号破壁後移動cpp

[白俊]2667号団地番号問題リンク
この問題はbfsで解決した.パスに重みを設定する最短パス検索は、dfsを使用して解くのが望ましいが、重みのない最短パスはbfsを使用して解くべきである.一定の経路を経て、初めて特定のセルに到達した場合、経路の長さが最小になることは保証されないからです.

・主なアイデア

この問題は一般的なbfs問題とあまり変わらないように見えますが、「必要であれば壁を除去できる」という条件が含まれています.これは論理に大きな影響を及ぼす.
つまり.

壁を壊さずに移動するアクセス情報

壁破壊状態に移動したアクセス情報

共同で管理しなければならない.始点から終点まで、終点ではなくある点に到達し、移動経路の長さが移動経路の長さと同じであれば、破壊しないほうがいい(壁を取り外して破壊し、破壊が非常に混乱している).これは、進む道に「破らなければならない」壁がある可能性があるからです.
したがって、破壁移動の距離が非破壁移動の距離と等しい場合、当然、非破壁移動の方法が選択される.あるいは、壁を壊すと距離がずいぶん短くなりますが、壁を壊さずに迂回すれば、もっと長い時間で着くことができ、この経路も意味のある経路になります.
このため、「壁を破壊せずに移動するアクセス情報」と「壁を破壊した場合に移動するアクセス情報」とが一緒に管理される.

・アルゴリズム

bfsを用いて、ルックアップアルゴリズムにおける「この点が可動点であるかどうか」、「その点にアクセスしたレコードがあるかどうか」を判断し、両方の条件が満たされた場合、次のアクセスポイントに追加する.これをcppコードとして記述すると、以下のように表すことができる.

if(!map[nextY][nextX] && !visit[nextY][nextX]) { ... } // map 변수는 길이 1, 벽이 0

「しかし、今回の問題は状況が違う」「壁を破壊したかどうか」の情報に基づいて、特定の場所にアクセスできるからです.この問題では、次の場所に回るために確認が必要な場合は2つに分けられます.

次の場所は「道」で訪問したことがない

次の場所は「壁」で、壁を壊したことはありません.

次の場所が壁の場合、その場所を訪問したことがなくても、壁を壊した記録があればどうせ行けないので、訪問の有無を確認する必要はありません.以降の内容では、壁を破壊するか否かをbreakingという変数で表現する.また、上記条件を満たす場合、次の場所に移動するには、以下の処理が必要となる.

次の場所は「道」で訪問したことがない
変更しない

breakingの場合、次のポイントをキューに入れます.

次の場所は「壁」で、壁を壊したことはありません.

breakingをtrueにし、次のポイントをキューに入れます.

上記の場合、breakingfalseからtrueに変更できますが、trueからfalseに変更することはできません.つまり、壁を打ち砕かずに破砕した状態にすることはできるが、破砕した事実を隠すことはできない.
これらのコンテンツを整理して生成される完全なソースコードは、次のとおりです.

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

struct state{
    int x;
    int y;
    int breaking;
};

std::pair<int, int> direction[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int rowSize, colSize;
int map[1000][1000];

int visit[1000][1000][2]; // 벽을 부수지 않은 상태 = 0, 벽을 부순 상태 = 1
std::queue<state> q;

int bfs(){
    while(!q.empty()){
        state cur = q.front();
        q.pop();
        if(cur.x == colSize - 1 && cur.y == rowSize - 1){ 	// 큐의 원소들을 따라 도착 지점에 도달한
            return visit[cur.y][cur.x][cur.breaking];		// 첫 번째 경로가 최단 경로임이 보장되기 때문에 
        }													// 도착 지점에 도달하자마자 bfs 중단

        for(auto dir : direction){
            int nextX = cur.x + dir.second;
            int nextY = cur.y + dir.first;

            if(nextX < 0 || nextX >= colSize || nextY < 0 || nextY >= rowSize){
                continue;
            }
            if(map[nextY][nextX] == 1 && !cur.breaking){
                q.push({nextX, nextY, 1});
                visit[nextY][nextX][1] = visit[cur.y][cur.x][cur.breaking] + 1;
            }
            else if(map[nextY][nextX] == 0 && !visit[nextY][nextX][cur.breaking]){
                q.push({nextX, nextY, cur.breaking});
                visit[nextY][nextX][cur.breaking] = visit[cur.y][cur.x][cur.breaking] + 1;
            }
        }
    }

    return -1;	// 도착 지점에 도달하지 못한 채로 bfs가 종료되면 -1을 반환
}

int main(){
    scanf("%d %d", &rowSize, &colSize);
    for(int row = 0; row < rowSize; row++){
        std::string line;
        std::cin >> line;

        for(int index = 0; index < colSize; index++){
            map[row][index] = line[index] - '0';
        }
    }

    q.push({0, 0, 0});
    visit[0][0][0] = 1;

    printf("%d", bfs());
}