7037：网格路径

题目描述

给定一张 $n\times n$ 的网格图，有些格子能走，有些格子不能走，左上角的格子坐标为 $(1,1)$，右下角的格子坐标为 $(n,n)$。

问最多可以找到多少条从 $(1,1)$ 到 $(n,n)$ 的不相交路径，使得每条路径经过的每个格子（包含 $(1, 1)$ 和 $(n, n)$）都是能走的格子？

每次我们只可以向右或向下走，不能离开网格图的边界。两条路径不相交当且仅当除了格子 $(1,1)$ 和 $(n,n)$，它们没有任何公共部分。

输入解释

第一行一个整数 $test(1\leq test \leq 1000)$ 表示数据组数。

对于每组数据，第一行一个整数 $n(2\leq n \leq 10)$ 表示网格图的大小。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串。第 $i$ 行第 $j$ 列的字符 '.' 表示 $(i,j)$ 可以走，'#' 表示不能走。

输出解释

对于每组数据，输出一行一个整数表示最多可以找到的不相交路径数目。

输入样例

3
2
..
..
3
...
.##
...
3
.#.
#..
...

输出样例

2
1
0

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021 年百度之星·程序设计大赛 - 初赛三

源链接： HDU-7037

最后修改于 2021-10-23T19:11:09+00:00 由爬虫自动更新

共提交 2 次

通过率 0.0%

时间上限	内存上限
2000/1000MS(Java/Others)	32768/32768K(Java/Others)