[BOJ]206-破壁と移動

https://www.acmicpc.net/problem/2206
質問する
N×Mのマトリックス表現のマッピングがあります.地図では、0は移動可能な位置、1は移動不可能な壁の位置を示す.(1,1)から(N,M)の位置に移動し、最短経路に移動します.最短パスとは、地図上の最小セルを通るパスで、開始セルと終了セルが含まれます.
移動中に壁を割ったり移動したりする経路がもっと短い場合は、壁を割って移動することができます.
1つのセルで移動できるセルは上下左右に隣接するセルです.
地図を指定すると、最短パスを解くプログラムが作成されます.
入力
第1行はN(1≦N≦1000),M(1≦M≦1000)を与える.次のN行はMの数字で地図を与えます.(1,1)と(N,M)は常に0であると仮定する.
しゅつりょく
1行目に最短距離を出力します.不可能な場合は-1を出力します.
サンプルI/O
入力

例1

6 4
0100
1110
1000
0000
0111
0000

例出力1

15

入力

例2

4 4
0111
1111
1111
1110

例出力2

-1

Solution

#include <iostream>
#include <deque>
#include <tuple>
#define MAX 1000

using namespace std;

int N, M;
int MATRIX[MAX][MAX];
int visit[MAX][MAX][2];

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

void BFS(){
    deque<tuple<int, int, int>> Q;
    Q.push_back({0, 0, 1});
    visit[0][0][1] = 1;
    while(!Q.empty()){
        int X , Y, block;
        tie(X, Y, block) = Q.front();
        Q.pop_front();
        if(X == N - 1 && Y == M - 1){
            cout << visit[X][Y][block] << "\n";
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = X + dx[i];
            int ny = Y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M){
                if(MATRIX[nx][ny] == 1 && block == 1){
                    visit[nx][ny][block - 1] = visit[X][Y][block] + 1;
                    Q.push_back({nx, ny, block - 1});
                }
                if(MATRIX[nx][ny] == 0 && visit[nx][ny][block] == 0){
                    visit[nx][ny][block] = visit[X][Y][block] + 1;
                    Q.push_back({nx, ny, block});
                }
            }
        }
    }
    cout << "-1\n";
    return;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        string tmp; cin >> tmp;
        for(int j = 0; j < M; j++) MATRIX[i][j] = tmp[j] - '0';
    }
    BFS();
}

BFSが適用されるかどうかの問題です.この問題はかなり難しい.
入力はstringでなければならないので、座標ごとにデータを入力する際にint型データを格納し、「0」を含まない.

void BFS(){
    deque<tuple<int, int, int>> Q;
    Q.push_back({0, 0, 1});
    visit[0][0][1] = 1;
    while(!Q.empty()){
        int X , Y, block;
        tie(X, Y, block) = Q.front();
        Q.pop_front();
        if(X == N - 1 && Y == M - 1){
            cout << visit[X][Y][block] << "\n";
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = X + dx[i];
            int ny = Y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M){
                if(MATRIX[nx][ny] == 1 && block == 1){
                    visit[nx][ny][block - 1] = visit[X][Y][block] + 1;
                    Q.push_back({nx, ny, block - 1});
                }
                if(MATRIX[nx][ny] == 0 && visit[nx][ny][block] == 0){
                    visit[nx][ny][block] = visit[X][Y][block] + 1;
                    Q.push_back({nx, ny, block});
                }
            }
        }
    }
    cout << "-1\n";
    return;
}

既存のBFSとは異なり2つのケースに分けられる.
1.壁を確認したらブロック(壁を割ったのか?)変数値は1ですか?
-この場合、壁を一度に砕くだけで済むと仮定します.
2.アクセスされていない0が見つかりました.
-既存のBFSと同様に行う.
これは,キューに座標情報を格納するだけでなく,壁を打ち砕くか否かの情報を格納して処理する方法である.そして全部で2つのvisitが並んでいます.
壁を壊したとき、壊さなかったとき.
この二つの状況が分割できるかどうかはこの問題の要求である.本当によく出てくるタイプなので、しっかり勉強すべきです.