Paizaの地図問題を解くときのメモ

Paizaで地図問題出るたびにいろいろ考えてると時間たりない

※「この記事は～」的な言い訳はめんどいので省略です。
正確な情報が必要な方は、ちゃんとした記事を参照ください。

※教本とかを見たとかではなく、独自の手法なので、より良い方法が世の中にはあるはず。

地図問題

通れるところを . で、通れないところを # で、
スタートを S で、ゴールを G で表すみたいなケース。

S . . . .
. # # . #
. . . # .
. . . . G

・最短距離は何歩か
・n回以内の方向転換でたどり着けるか
みたいな問題がありがちですね。

ボクは境界の判定が苦手なので、まず壁で囲ってしまいます。

# # # # # # #
# S . . . . #
# . # # . # #
# . . . # . #
# . . . . G #
# # # # # # #

これで「次に進むマスが範囲外か？」みたいな判定が不要になりますね

最短距離を求める

最短経路を求める際は、こういう地図を作りたいですね。

-1 -1 -1 -1 -1 -1 -1
-1  0  1  2  3  4 -1
-1  1 -1 -1  4 -1 -1
-1  2  3  4 -1  8 -1
-1  3  4  5  6  7 -1
-1 -1 -1 -1 -1 -1 -1

通れないところを-1、通れるところはスタートからの最短距離を入れていきます。
マスが少ない場合は「最短距離がn-1のマスを全探索して、隣のマスにnを入れる」を繰り返せばよいですが、
マスが多い場合は計算時間が足りなくなるので、「n-1を入れたマスを覚えておく」が必要になります。

int hight, width;
int area[10000][10000]; // 地図 (僕は #include <map> してるせいでmapと命名できない。。。)
vector<pair<int, int>> prev_list; // (y, x)座標
vector<pair<int, int>> next_list; // (y, x)座標

void check(int count) {
    for (auto itr: prev_list) {
        int y = itr.first; int x = itr.second;
        if (area[y-1][x] > count) {// 上
            area[y-1][x] = count;
            // 今回更新した座標を覚える
            next_list.push_back({y-1, x});
        }
        if (area[y+1][x] > count) {// 下
            area[y+1][x] = count;
            next_list.push_back({y+1, x});
        }
        if (area[y][x-1] > count) {// 左
            area[y][x-1] = count;
            next_list.push_back({y, x-1});
        }
        if (area[y][x+1] > count) {// 右
            area[y][x+1] = count;
            next_list.push_back({y, x+1});
        }
    }
    prev_list.clear();
    copy(next_list.begin(), next_list.end(), back_inserter(prev_list));
    next_list.clear();
}

int main(void){
    cin >> hight >> width;
    memset(area, 0xff, sizeof(area)); // 地図を-1(壁)埋め
    int s_y, s_x;
    
    for (int i = 0; i < hight; i++) {
        for (int j = 0; j < width; j++) {
            char c;
            cin >> c;
            if (c == '.' || c == 'G') {
                area[i + 1][j + 1] = INT_MAX; // 通れるところは INT_MAXに。
            }
            if (c == 'S') {
                area[i + 1][j + 1] = 0;
                s_y = i+1; s_x = j+1;
            }
        }
    }
        
    prev_list.push_back({s_y, s_x});
    int count = 1;
    while (prev_list.size() != 0) {
        check(count);
        count++;
    }

    return 0;
}

n回以内の方向転換でたどり着けるか

現在の方向、方向転換回数を引数にして、再帰呼び出しをする。
方向は u d l r で管理するとボクに対して可読性高いです。

void move(char direction, int turn, int y, int x) {
    // 方向転換回数チェック
    if (turn >= n) {
        return;
    }

    // ゴール判定
    if (y == g_y && x == g_x) {
        goal = true;
        return;
    }

    int next_y = y; int next_x = x;
    switch (direction) {
        case 'u' : next_y--; break;
        case 'd' : next_y++; break;
        case 'l' : next_x--; break;
        case 'r' : next_x++; break;
    }
    // 移動できるなら、そのままの方向に移動する
    if (check(next_y, next_x)) {
        move(direction, turn, next_y, next_x);
    }
    if (goal) return; // ゴールできたなら、終了


    // 方向転換回数を+1して、移動できるなら移動する。
    if (direction != 'u' && check(y-1, x)) { move('u', turn+1, y-1, x);} if (goal) return;
    if (direction != 'd' && check(y+1, x)) { move('d', turn+1, y+1, x);} if (goal) return;
    if (direction != 'l' && check(y, x-1)) { move('l', turn+1, y, x-1);} if (goal) return;    
    if (direction != 'r' && check(y, x+1)) { move('r', turn+1, y, x+1);} if (goal) return;    

    return;
}