• $Atcoder$·题目传送门。

• 此处食用效果更加。

• 题目翻译。

• $AT$官方·题解。

解题思路

由于 $ H $ 和 $ W $ 的值较小，可以使用深搜（DFS）来遍历所有可能的路径，同时记录已经访问过的单元格，以避免重复访问走回头路。

1. 首先遍历每个空单元格，作为起点。

2. 使用 $DFS$ 递归函数进行深搜，搜索路径长度为 $K$ 。

3. 在每一步中检查相邻的单元格，如果是空的并且未被访问过，则继续向该单元格移动。

4. 当路径长度达到 $K$ 时，计数有效路径。

5. 使用一个集合或数组记录已经访问过的单元格，在回溯时进行清理。

---

$AC$代码。

#include <bits/stdc++.h>
using namespace std;
int H, W, K;
char g[11][11]; // 网格
bool v[11][11]; // 访问标记
int  di[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右的移动方向
int t = 0;void dfs(int x, int y, int m)
{if (m == K){t++;return;}// 进行上下左右的移动for (int d = 0; d < 4; d++){int nx = x + di[d][0];int ny = y + di[d][1];// 检查新位置是否有效且未被访问if (nx >= 1 && nx <= H && ny >= 1 && ny <= W && g[nx][ny] == '.' && !v[nx][ny]){v[nx][ny] = true; // 标记访问dfs(nx, ny, m + 1); // 继续深度搜索v[nx][ny] = false; // 回溯，清理访问标记}}
}int main()
{cin >> H >> W >> K;for (int i = 1; i <= H; i++){for (int j = 1; j <= W; j++){cin >> g[i][j];}}// 从每个空单元格出发for (int i = 1; i <= H; i++){for (int j = 1; j <= W; j++){if (g[i][j] == '.'){memset(v, false, sizeof(v)); // 重置访问标记v[i][j] = true; // 标记起点已访问dfs(i, j, 0); // 开始 DFS}}}cout << t << endl; // 输出结果，记得换行return 0;//by NOIPwjy2011
}

$atcoder$ · $AC$记录。