周囲を探索しよう(4方向編)

はい、あるごりずむ。

今回はグリッド系（マス目系）の問題で任意のマス周りの周囲四方向を探索するアルゴリズムを紹介します。

 s
sos
 s

図1.今回はoのまわりのsの部分を探索するアルゴリズム

まずは観察

まずはこのアルゴリズムを実装する前に図1を観察してみましょう。

このままだとアルゴリズムに落としにくいので図2のように座標をとり、さらにxに反時計回りに番号をつけておきます。

下方向を正、右方向を正として原点(row, col) = (0,0)を周囲を探索したいマスに置きます。

         |s1(-1, 0)|
s2( 0,-1)| o( 0, 0)|s4( 0, 1)
         |s3( 1, 0)|

図2.座標として置くと？

こうすると

(s1のrow) = (oのrow) + -1
(s1のcol) = (oのcol) +  0

(s2のrow) = (oのrow) +  0
(s2のcol) = (oのcol) + -1

(s3のrow) = (oのrow) +  1
(s3のcol) = (oのcol) +  0


(s4のrow) = (oのrow) +  0
(s4のcol) = (oのcol) +  1

図3.式に落とせる！

となっていることが分かります。

このアルゴリズムを実装するためには単純に上の式をプログラムに落とせば良さそうですね。

実装するか

さて観察からこのアルゴリズムを図3で書いた式をそのままに実装します。

#1#
6o2
#5#

図4.例題1の入力

今回は上の図のo周りに数字の和を求めるプログラムを例として紹介します。

#include <iostream>
#include <vector>
#include <string>

int main(void) {
    vector<string> field(3); //3行分の文字列を確保。
    for (int row = 0; row < 3; row++) cin >> field[row]; //入力を文字列のvectorに読み込み
    
    int o_row,o_col;
    o_row = 1; o_col = 1; 
    //"まずは観察"の例とは異なり
    //oの座標が(row, col) = (1,1) であることに注意。
    int sum = 0;

    sum += field[o_row + (-1)][o_col +    0] 
    // (s1のrow) = (oのrow) + -1
    // (s1のcol) = (oのcol) +  0

    sum += field[o_row +    0][o_col + (-1)]
    // (s1のrow) = (oのrow) +  0
    // (s1のcol) = (oのcol) + -1

    sum += field[o_row +    1][o_col +    0]
    // (s1のrow) = (oのrow) +  1
    // (s1のcol) = (oのcol) +  0

    sum += field[o_row +    0][o_col +    1]
    // (s1のrow) = (oのrow) +  0
    // (s1のcol) = (oのcol) +  1

    cout << sum << endl;
    
    return 0;
}

最後に確認

面倒くさくなったので明日書きます。