Farma's Study Desk

2次元グリッド上探索まとめ

Tips Probramming Contest Search algorithm C++

グリッド上探索の概要

　ここでは以下のような4方位もしくは8方位上の探索についてまとめる。

f:id:farma_11:20171107231155p:plain — Fig 1. グリッドの例

　画像上の赤い点からそれぞれの方位に1区画の部分に移動する際のことを考える。このとき、以下のように dx[] や dy[] などの配列を用いて各方位1マス先の座標を計算し、順にそのマスにおける処理をしていく。探索法としては、先に深度の大きい側を優先しているため、深さ優先探索 (DFS: Depth-First Search)を用いていることとなる。

コーディング例

4方位の場合 ver.1

int dx[4]={ 0, 1, 0,-1}; // x軸方向への変位
int dy[4]={ 1, 0,-1, 0}; // y軸方向への変位
int dfs(int x, int y){

    // 周囲4方位のマスを探索
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        dfs(nx, ny);
    }
}

4方位の場合 ver.2

int d[5]={ 0, 1, 0,-1, 0};
int dfs(int x, int y){

    for(int i = 0; i < 4; i++){
        int nx = x + d[i], ny = y + d[i+1];
        dfs(nx, ny);
    }
}

4方位の場合 ver.3

int d[4]={ 0, 1, 0,-1};
int dfs(int x, int y){

    for(int i = 0; i < 4; i++){
        int nx = x + d[i], ny = y + d[(i+1) & 3];
        dfs(nx, ny);
    }
}

　4方位の場合は上記の通り、いくつかパターンが存在している。 versionが進むにつれ、使用するメモリ量が小さくなっていくが、個人的にはどれもメモリ量に差は大きくなく、 ver.1が一番わかりやすくミスを防ぎやすいと考えているためver.1をいつも利用している。

8方位の場合 ver.1

int dx[8]={ 0, 1, 0,-1, 1, 1,-1,-1}; // x軸方向への変位
int dy[8]={ 1, 0,-1, 0, 1,-1, 1,-1}; // y軸方向への変位
int dfs(int x, int y){

    // 周囲8方位のマスを探索
    for(int i = 0; i < 8; i++){
        int nx = x + dx[i], ny = y + dy[i];
        dfs(nx, ny);
    }
}

8方位の場合 ver.2

int d[9]={ 0, 1, 0,-1, 1, 1,-1,-1, 0};
int dfs(int x, int y){

    for(int i = 0; i < 8; i++){
        int nx = x + d[i], ny = y + d[i+1];
        dfs(nx, ny);
    }
}

8方位の場合 ver.3

int dfs(int x, int y){

    for(int dx = -1; dx <= 1; dx++){
        for(int dy = -1; dy <= 1; dy++){
            int nx = x + dx, ny = y + dy;
            dfs(nx, ny);
        }
    }
}

　このテクニックは、将棋の桂馬の動きであったとしても、3次元ベクトル空間上の格子点走査であったとしても応用しやすいとても基本的で実用的であると思います。競技プログラミングを始めて、初めて覚えるテクニックのひとつなのかもしれません。

練習問題