No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

接下来我们看怎么求解一个迷宫有多少种可行的路径，这个其实比较简单，就声明一个全局变量表示结果，然后每次搜到终点就把结果加 11 就好了，这个函数也不必有返回值了。

写下代码来就是

int ans = 0; // 全局变量自动清 0 ，所以不手动初始化也行
int dir[4][2] = { { -1, 0},{0, -1},{1, 0},{0, 1}};
void dfs(int x, int y) {
    if (maze[x][y] == 'T') {
        ans++;
        return;
    }
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
            dfs(tx, ty);
        }
    }
    vis[x][y] = false;
}

接下来我们思考一个问题，在求解迷宫可行性，就是能不能从起点走到终点的过程中我们是没有取消访问标记的，因为如果这个点之前访问过已经判断出不可行了，那就没有必要再去那个点走一遍了。

但是现在求解的个数的时候是取消了标记的，这是为什么？

因为现在如果通过不同的方案到了同一个点，是需要再往后走的，它到这个点以后还能往后有多少条路径也跟是怎么到这个点有关的，所以没有什么好办法，只能取消标记，让它每次都重新尝试走。

所以判可行性时可以不取消，但是如果求解迷宫的解数相关的问题就必须要取消标记把每条路都跑完。