実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 587

問題概要

$H \times W$ のマス目があり、マス目の上から $i$ 番目、左から $j$ 番目のマスをマス $(i, j)$ と表す。また、マス $(i, j)$ は $S_{i, j}$ が.のとき空きマスであり、#のとき障害物が存在する。

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

制約

$H,W,K$ は整数。
$1 \leq H,W \leq 10$
$1 \leq K \leq 11$
空きマスが少なくとも1つ存在する。

考察

注目すべきは $1 \leq H,W \leq 10, \quad1 \leq K \leq 11$ という制約の小ささである。しかも、ご丁寧にサンプルケース3で制約の最大ケースが与えられている。これを見ると、条件を満たす経路の個数は 210000 個程度であると推測できる。

これは実際正しくて、

スタートのマスの決め方 : $HW$ 通り
1回目の移動先 : スタートマスの周囲の4マスだから $4$ 通り
$i \: (2 \leq i \leq K)$ 回目の移動先 : $i - 1$ 回目のマスの周囲の4マスのうち、 $i - 2$ 回目で訪れなかったマスだから高々 $3$ 通り

より、高々 $HW \cdot 4 \cdot 3^{K-1} = 23619600 \approx 2.3 \times 10^7$ 通りとなる。

この程度であれば、全探索できそうだ。

グリッド上の全探索には、 BFS または DFS が有効だ。今回も DFS の再帰処理によって効率的な全探索を行うことができる。

具体的には、今いるマスの位置とこれまでの移動回数、そして訪問済みのマスのフラグ配列を用意しておき、各マスにおいてその4近傍のマスを再帰的に探索するというものだ。

なお、コードではmain関数の外部に DFS の処理を書いているので引数の数がとんでもないことになっているが、 C++ ではラムダ式を使うことでちょっと簡潔なコードにすることができる。ただ、色々デメリットもあるので詳しくは以下の記事を参照。

qiita.com

koturn.hatenablog.com

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(vector<string> &grid, vector<vector<bool>> &visited, const int &H, const int &W, const int &K, int x, int y, int steps, int &ans)
{
    if (steps == K)
    {
        ans++;
        return;
    }

    visited[x][y] = true;

    rep(dir, 0, 4)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] == '.' && !visited[nx][ny])
        {
            dfs(grid, visited, H, W, K, nx, ny, steps + 1, ans);
        }
    }

    visited[x][y] = false;
}

int main()
{
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> grid(H);
    rep(i, 0, H) cin >> grid[i];
    vector<vector<bool>> visited(H, vector<bool>(W, false));

    int ans = 0;
    rep(i, 0, H) rep(j, 0, W)
    {
        if (grid[i][j] == '.')
            dfs(grid, visited, H, W, K, i, j, 0, ans);
    }

    cout << ans << endl;
}