//Coder: Balajiganapathi #define TRACE #define DEBUG #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector vi; typedef pair pi; typedef vector vs; // Basic macros #define st first #define se second #define all(x) (x).begin(), (x).end() #define ini(a, v) memset(a, v, sizeof(a)) #define re(i,s,n) for(int i=s;i<(n);++i) #define rep(i,s,n) for(int i=s;i<=(n);++i) #define fr(i,n) re(i,0,n) #define repv(i,f,t) for(int i = f; i >= t; --i) #define rev(i,f,t) repv(i,f - 1,t) #define frv(i,n) rev(i,n,0) #define pu push_back #define mp make_pair #define sz(x) (int)(x.size()) const int oo = 2000000009; const double eps = 1e-9; #ifdef TRACE #define trace1(x) cerr << #x << ": " << x << endl; #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl; #define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl; #define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl; #define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl; #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl; #else #define trace1(x) #define trace2(x, y) #define trace3(x, y, z) #define trace4(a, b, c, d) #define trace5(a, b, c, d, e) #define trace6(a, b, c, d, e, f) #endif const int mx = 1003; char b[mx][mx]; int n, m, cnt; int vis[mx][mx]; //Store info of a single connected component. struct Comp { public: //(si, sj) starting point and (ei, ej) ending point of the rectangle containing the component int si, sj, ei, ej; Comp() {} Comp(int i1, int j1, int i2, int j2) { si = i1; sj = j1; ei = i2; ej = j2; } } comps[mx * mx]; int si, sj, ei, ej; //Find a connected component and its bounding rectangle void dfs(int i, int j) { if(i < 0 || i >= n || j < 0 || j >= m || b[i][j] != 'W' || vis[i][j]) return; vis[i][j] = 1; si = min(si, i); sj = min(sj, j); ei = max(ei, i); ej = max(ej, j); dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1); } //Events of a single axis. type = 1 means starting and 0 means ending class Event { public: int type, idx, x; Event() {} Event(int t, int _x, int i) { type = t; idx = i; x = _x; } bool operator < (const Event &ev) const { if(x != ev.x) return x < ev.x; return type < ev.type; } } events_i[2 * mx * mx]; int main() { int t; cin >> t; while(t--) { multiset setj1, setj2; cin >> n >> m; fr(i, n) cin >> b[i]; cnt = 0; ini(vis, 0); //Calculate bounding rectangle of each component fr(i, n) fr(j, m) if(b[i][j] == 'W' && !vis[i][j]) { si = sj = oo; ei = ej = -oo; dfs(i, j); if(si == 0 || sj == 0 || ei == n - 1 || ej == m - 1) continue; --si; --sj; ++ei; ++ej; comps[cnt] = Comp(si, sj, ei, ej); events_i[2 * cnt] = Event(1, si, cnt); events_i[2 * cnt + 1] = Event(0, ei, cnt); setj1.insert(sj); setj2.insert(ej); ++cnt; } //setj1 and setj2 has the starting and ending columns of comps not covered by i currently setj1.insert(-oo); setj2.insert(oo); sort(events_i, events_i + 2 * cnt); bool pos = (cnt == 0); int cnti = 0; //Fix a row i to spray //We need only consider end points of bounding rectangles for this fr(i, 2 * cnt) { int idx = events_i[i].idx; if(events_i[i].type == 0) { // If ending event then add corresponding columns to setj1 and setj2 setj1.insert(comps[idx].sj); setj2.insert(comps[idx].ej); --cnti; } else { //If starting event then delete the columns setj1.erase(setj1.find(comps[idx].sj)); setj2.erase(setj2.find(comps[idx].ej)); ++cnti; } //So we have fixed a row and we have a set of columns which are not covered by that row. If the set of colums has a non empty intersection then we can choose any column in the intersection. if(*setj1.rbegin() <= *setj2.begin()) { //Non empty intersection. We have found a solution pos = 1; break; } } printf("%s\n", pos? "YES": "NO"); } return 0; }