幅優先探索

最短経路問題

問題　:　動作確認済み

queue と vector を使う

int H, W; // 迷路の大きさ
char c[1009][1009]; // x座標、y座標
int dist[1009][1009]; //縦、横

void print(char c[1009][1009])
{
    rep(i, 0, H + 2)
    {
        rep(j, 0, W + 2) cout << c[j][i] << " ";
        cout << endl;
    }
}

int main() {
    // 迷路を入力する
    //cin >> H >> W; // 縦、横の長さ
    cin >> W >> H; // 横、縦の長さ

    /*周りを壁で囲う場合
    rep(i, 0, H + 2)rep(j, 0, W + 2)
        c[j][i] = '.'; // '.' 通路、'#' 障害物

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++)
        {
            cin >> c[j][i]; 
        }
    }
    
    //print(c);
    */
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) cin >> c[j][i]; //壁かマスか
    }

    // 各マスの最短距離
    for (int i = 0; i < H + 2; i++) {
        for (int j = 0; j < W + 2; j++) dist[j][i] = 1000000007; // x座標、y座標
    }

    // 幅優先探索により、最短移動回数を求める
    queue<pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    dist[0][0] = 0; // スタート地点

    while (!Q.empty()) {
        int cx = Q.front().first, cy = Q.front().second;
        Q.pop();

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

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

        for (int i = 0; i < 6; i++) {
            int ex = cx + dx[cy % 2][i], ey = cy + dy[i];

            //周りの壁がなければ範囲指定する
            if (!(0 <= ex && ex <= W + 1 && 0 <= ey && ey <= H + 1)) continue;

            //1づつ増加するため、塗り替えない
            if (c[ex][ey] != '.' || dist[ex][ey] != 1000000007) continue;


            Q.push(make_pair(ex, ey));
            dist[ex][ey] = dist[cx][cy] + 1;
        }
    }

    return 0;
}