#1027. 不喜欢拐弯 3 一秒512M
不喜欢拐弯 3 一秒512M
当前没有测试数据。
题目描述
一个 N×N 的棋盘,你要从左上角走到右下角,只能竖直向下走或水平向右走,不能走出棋盘外。每个格子要么是黑色,要么是白色。你不喜欢黑色,所以你绝不会踏入黑格子。你也不喜欢拐弯,所以在路途中,你不会拐弯超过 K 次。问:你有多少条不同的路线?
注:在起点处你可以任选一个方向开始行走,不计入拐弯次数。
输入格式
第一行两个整数 N, K。
接下来是一个 N×N 的字符矩阵,只包括两种字符:.,H,其中 . 表示白格子,H 表示黑格子。数据保证起点和终点是白格子。
输出格式
一个整数,表示不同路线条数。答案可能很大,你需要将答案对 998244353 取模后输出
样例输入
4 3
...H
.H..
....
H...
样例输出
6
数据范围
所有测试点满足:2≤N≤300,1≤K≤2×N-3