#1833. AT_abc386_d-Diagonal Separation
AT_abc386_d-Diagonal Separation
Problem Statement
There is an grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:
For every row, the following condition holds:
There exists an integer such that the leftmost cells are colored black, and the rest are colored white.
For every column, the following condition holds:
There exists an integer such that the topmost cells are colored black, and the rest are colored white.
Out of these cells, of them have already been colored. Among them, the -th one is at the -th row from the top and the -th column from the left, and it is colored black if is B and white if is W. Determine whether he can color the remaining uncolored cells so that all the conditions are satisfied.
Constraints
is B or W. All input numbers are integers.
Sample Input 1
4 3
4 1 B
3 2 W
1 3 B
Sample Output 1
Yes
For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.
Sample Input 2
2 2
1 2 W
2 2 B
Sample Output 2
No
No matter how the remaining two cells are colored, the conditions cannot be satisfied.
Sample Input 3
1 1
1 1 W
Sample Output 3
Yes
Sample Input 4
2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B
Sample Output 4
No