問題概要

$H \times W$ グリッドで、各マスは「空き」または「壁」である。

ある空きマスを出発し、上下左右に隣接するマスへの移動を $K$ 回行う方法であって、障害物のあるマスを通らず、同じマスを 2 回以上通らないようなものの個数を求めよ。

制約

$1 \le H, W \le 10$
$1 \le K \le 11$

考えたこと

これは全探索！！！！！！

そして、ほとんど同じ問題が過去に JOI でも出題されている。解法や実装方針の詳細は、下の記事に書いた。

drken1215.hatenablog.com

コード

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

vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    long long res = 0;
    vector<vector<int>> used(H, vector<int>(W, 0));
    auto rec = [&](auto rec, int x, int y, int rem) -> void {
        if (rem == 0) {
            res++;
            return;
        }

        used[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int x2 = x + dx[d], y2 = y + dy[d];
            if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) continue;
            if (S[x2][y2] == '#' || used[x2][y2]) continue;
            rec(rec, x2, y2, rem-1);
        }
        used[x][y] = false;
    };

    for (int x = 0; x < H; x++) for (int y = 0; y < W; y++) {
        if (S[x][y] == '#') continue;
        used.assign(H, vector<int>(W, 0));
        rec(rec, x, y, K);
    }
    cout << res << endl;
}