All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.El Macho's army of mutated minions is marching towards Gru, the army is standing in a rectangular formation measuring NxM. The spray of antidotes done by Gru has turned some of the minions back to normal, but now they are trapped within the army of mutated ones. Formally, a normal minion is "not trapped" if :
1) either he is on one of the edges of the rectangle
2) or one of his direct neighbors (directly in front/back of him, or left/right of him) is not trapped.
Any trapped minion will be killed by the mutated minions, which Gru cannot let happen. Gru will use his antidote ray to turn exactly one row and one column of the army to normal minions. If there are any normal minions in that row or column, they remain unaffected. Can Gru select a row and a column such that no normal minion remains trapped after the antidote ray?
First line contains T, number of testcases
Each testcase starts with a line containing two space separated integers N and M.
N lines follow, each containing M characters. jth character of the ith line is "B" if the minion at ith row and jth column in the army is mutated, "W" otherwise.
Print "YES or "NO" (quotes for clarity) to indicate wheather it is possible for Gru to save the trapped minions.
30 points : 1<=N,M<=100
70 points : 1<=N,M<=1000
Any row and column pair selected by Gru guarantees that the trapped minion does not remain trapped.
|Tags||dynamic-programming, easy-medium, ltime11, piyushkumar, prefix-sums|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.