#P4171. [2015年湖南省队省队集训]Rhl的游戏

    ID: 3386 传统题 1000ms 128MiB 尝试: 109 已通过: 30 难度: 6 上传者: 标签>难度分类提高+/省选-线性代数与代数GF(2) 消元增广矩阵CF2100

[2015年湖南省队省队集训]Rhl的游戏

[2015 湖南省队集训] Rhl 的游戏

题目描述

RHL 在一个 nn 行 mm 列的黑白网格上玩 Flip it。按下一格会翻转该格和它所有共边相邻格子的颜色:黑变白、白变黑。坏掉的格子不能被按下,仍然会受相邻格子的按压影响。

判断能否通过若干次按压将全部格子变成白色。

输入格式

第一行一个整数 TT(1≤T≤101\le T\le10),表示数据组数。

每组第一行三个整数 n,m,kn,m,k(1≤n,m≤2561\le n,m\le256,0≤k≤2560\le k\le256),分别表示网格的行数、列数和坏格个数。随后 nn 行,每行一个长度为 mm 的字符串,B 表示黑色,W 表示白色。最后 kk 行,每行两个整数 xi,yix_i,y_i(1≤xi≤n1\le x_i\le n,1≤yi≤m1\le y_i\le m),表示一个坏格的行号和列号。

输出格式

对第 ii 组数据,先输出一行 Case #i:(将 i 替换成从 11 开始的组号),再另起一行。若能将所有格子变白,输出 YES,否则输出 NO。

样例 #1

样例输入 #1

2
3 3 0
WBW
BBB
WBW
3 3 2
WBW
BBB
WBW
2 2
3 2

样例输出 #1

Case #1:
YES
Case #2:
NO