#1026. 不喜欢拐弯 2
不喜欢拐弯 2
题目描述
一个 N×N 的棋盘,你要从左上角走到右下角,只能竖直向下走或水平向右走,不能走出棋盘外。每个格子要么是黑色,要么是白色。你不喜欢黑色,所以你绝不会踏入黑格子。你不喜欢拐弯,但有时候这可能是无法避免的。不过你也有自己的原则,你绝不会拐弯超过 K 次。问:你有多少条不同的路线?
注:在起点处你可以任选一个方向开始行走,不计入拐弯次数。
输入格式
多组数据。
第一行:一个整数 T 表示数据组数。
对于每组数据:
-第一行两个整数 N, K。
接下来是一个 N×N 的字符矩阵,只包括两种字符:W,B,其中 W 表示白格子,B 表示黑格子。数据保证起点和终点是白格子。
输出格式
T 行,每组数据的答案占一行
样例输入
5
3 1
WWW
WWW
WWW
3 2
WWW
WWW
WWW
3 3
WWW
WWW
WWW
3 2
WBB
BBB
BBW
4 3
WWWB
WBWW
WWWW
BWWW
样例输出
2
4
6
0
6
数据范围
所有测试点满足:1≤T≤50,2≤N≤50,1≤K≤3,其中:
- 10%的数据 满足 。
- 30%的数据 满足 。
- 60%的数据 满足 。