2行×n列のグリッドでロボットがゴールに到達できるか判定するC++コード

問題の概要

2行・n列のグリッドが与えられます。ロボットはグリッド上の位置 (0, 0) におり、現在位置から上下左右および斜め（角）に隣接するセルへ移動しながら、(1, n − 1) のセルを目指します。

グリッドは文字列の配列として渡され、各セルは次のように表されます。

• # … ブロックされていて通行できないセル
• . … 通行可能なセル

このとき、ロボットが (0, 0) から出発して (1, n − 1) に到達できるかどうかを判定します。

例えば、入力が n = 4、grid = {".##.", "...."} の場合、出力は「Possible（到達可能）」となります。

解法の考え方

この問題は、以下の手順で解くことができます。

1. フラグを 1 で初期化します。
2. 各列 i について走査し、grid[0][i] と grid[1][i] がどちらも「#」である場合は、フラグを 0 に設定します。
3. 最後にフラグの値を確認し、0 であれば「Not Possible.」を、そうでなければ「Possible.」を出力します。

ロボットは斜め移動もできるため、各列で少なくとも片方のセルが開いていれば、上下の行を行き来しながら右へ進むことができます。一方、ある列の上下両方がブロックされていると、その列を越えて先に進むことはできません。したがって、「完全に塞がれた列が存在するかどうか」を全列チェックすればよいのです。

擬似コード

flag := 1
for initialize i := 0, when i < n, update (increase i by 1), do:
    if grid[0, i] is same as '#' and grid[1, i] is same as '#', then:
        flag := 0
if flag is same as 0, then:
    print("Not Possible.")
Otherwise
    print("Possible.")

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, string grid[]) {
    int flag = 1;
    for(int i = 0; i < n; i++){
        if(grid[0].at(i) == '#' && grid[1].at(i) == '#'){
            flag = 0;
        }
    }
    if (flag == 0)
        cout<<"Not Possible.";
    else
        cout<<"Possible.";
}
int main() {
    int n = 4;
    string grid[] = {".##.", "...."};
    solve(n, grid);
    return 0;
}

入力

4, {".##.", "...."}

出力

Possible.

この実装では、グリッドの全列を一度だけ走査するため、計算量は O(n)、追加のメモリも定数個の変数だけで済む、非常に効率的なアルゴリズムとなっています。