GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A1662. $小码君的路$

编程题普及/提高-

知识点

字符串线性动态规划

题目描述

小码君有一个 $2\times m$ 的矩阵，矩阵中只可能包含字符 B 和 W。每一列都有字符 B。问能否找出一条路径，满足： - 路径中相邻两格有公共边（只有公共点的不算）。 - 每个 B 格恰好被覆盖一次。 - 每个 W 格都没有被覆盖到。 如果存在这样的路径，输出 YES，否则输出 NO。

输入格式

先输入一个t表示有t个矩阵 输入一个m表示矩阵的长

输出格式

如果存在这样的路径，输出 YES ，否则输出 NO

输入输出样例

输入 #1

6
3
WBB
BBW
1
B
B
5
BWBWB
BBBBB
2
BW
WB
5
BBBBW
BWBBB
6
BWBBWB
BBBBBB

输出 #1

YES
YES
NO
NO
NO
YES

上一题去做题下一题