プログラミングと絵と音楽

コンピューター科学を専攻し、絵と音楽を趣味とするエンジニアのブログです。

到達可能問題を解く

ある場において出発地点、目的地点、通過可能な場所が与えられた時、出発地点から目的地点までたどり着くことが可能かどうかを判定する到達可能問題を解こうと思います。

問題を想定します。幅 width 高さ height の場が与えられ、出発地点と目的地点が与えられるとします。移動は上下左右の4方向のうち、通過可能である場所のみとします。

この問題は、幅優先探索深さ優先探索どちらを用いても求められます。
まず深さ探索における解き方について考えてみましょう。
ある地点 x, y において到達可能 search(x, y) としましょう。このとき、

  • 上下左右のいずれかで移動可能な場所において、また同様の探索 search(x, y) を行います。
  • もし目的地点が隣にあれば、到達可能。
  • いずれも移動可能でなければ、到達不可能。

というように再帰的な考え方で解けます。

実際に C++ で実装したものになります。

#include <iostream>

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

bool search(char **field, int width, int height, int x, int y){
    field[y][x] = '.';

    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(nx < 0 || nx >= width || ny < 0 || ny >= height){
            continue;
        }

        char c = field[ny][nx];

        if(c == '#'){
            if(search(field, width, height, nx, ny)){
                return true;
            }
        }else if(c == 'G'){
            return true;
        }
    }

    return false;
}

int main(){
    int width, height;
    char **field;
    int sx, sy;

    std::cin >> width >> height;

    field = new char*[height];
    for(int i = 0; i < height; i++){
        field[i] = new char[width];
        for(int j = 0; j < width; j++){
            char v;
            std::cin >> v;
            field[i][j] = v;
            if(v == 'S'){
                sx = j;
                sy = i;
            }
        }
    }

    if(search(field, width, height, sx, sy)){
        std::cout << "possible" << std::endl;
    }else{
        std::cout << "impossible" << std::endl;
    }

    for(int i = 0; i < height; i++){
        delete [] field[i];
    }
    delete [] field;

    return 0;
}

入力はこちら、入力1は possible を返します。

8 6
S # . . # # # .
. # . # # . # .
# # # # . . # .
. . . # . . . .
. # # # # # # .
. # # . . . # G

入力2は随分と回り道ですが、到達可能なので possible を返します。

8 12
# # # # . # # #
# . . # . # . #
# . . # # # . #
# # . . . . . #
. # . G # # # #
. # . . . . . .
. # # # # # # #
# . . . . . . #
# . . . . . . #
# # # # # # . #
# . . S . # . #
# . . . . # # #

入力3は到達できないので impossible を返します。

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

search(x, y) は到達可能な x, y において、隣をさらに探索する関数です。ここに到達可能である出発地点を入力して探索を行います。既に到達した場所に戻らないように、到達した場所は移動不可能としておくことで無限の繰り返しを避けます。実は再帰関数を使わなくてもスタックを使うことで解くこともできます。

幅優先探索での解法は、基本的な考え方は深さ優先探索での解法と同じですが、キューを用います。キューに到達可能地点(初期状態では出発地点)を入力し、キューから一つずつ取り出しながら、隣が移動可能ならばそれをキューに新たに突っ込むというのを繰り返します。
これは Python で書きました。

import queue

def main():
    [width, height] = [int(x) for x in input().split()]
    field = []
    q = queue.Queue()
    dw = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    for i in range(height):
        line = input().split()
        field.append(line)
        for j in range(width):
            if field[i][j] == "S":
                q.put((i, j))

    flag = False

    while not q.empty():
        (y, x) = q.get()
        field[y][x] = "."
        for (dx, dy) in dw:
            nx = x + dx
            ny = y + dy
            if nx in range(width) and ny in range(height):
                if field[ny][nx] == "#":
                    q.put((ny, nx))
                elif field[ny][nx] == "G":
                    flag = True
                    while not q.empty():
                        q.get()

    if flag:
        print("possible")
    else:
        print("impossible")

if __name__ == '__main__':
    main()