Official

F - 将棋のように/Like As Shogi Editorial by penguinman


入力のサイズが定数個でかつ非常に小さいので、全てのマスについてそのマスに到達可能かを場合分けによって判定することも不可能ではないでしょう。しかし、この問題を解くだけであれば素直に幅優先探索と呼ばれるアルゴリズムを用いてマス目上を機械的に走査するのが賢明です。

計算量はマス目のサイズの定数倍に収まり、非常に高速です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int A,B; cin >> A >> B;
    int N = 9;
    vector<string> S(3);
    for(auto &el: S) cin >> el;
    A--, B--;
    vector<vector<bool>> flag(N,vector<bool>(N));
    flag[A][B] = true;
    queue<pair<int,int>> que;
    que.push(make_pair(A,B));
    while(!que.empty()){
        auto p = que.front(); que.pop();
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                int x = p.first+i-1;
                int y = p.second+j-1;
                if(0<=x && x<N && 0<=y && y<N && S[i][j]=='#' && !flag[x][y]){
                    flag[x][y] = true;
                    que.push(make_pair(x,y));
                }
            }
        }
    }
    int ans = 0;
    for(auto p: flag){
        for(auto q: p) ans += q;
    }
    cout << ans << endl;
}

posted:
last update: