CodeForces 275B Convex Shape
http://codeforces.com/problemset/problem/275/B
2回以上曲がらずに任意の黒から任意の黒に行けるかという問題
本番では幅優先をした。でもよく考えたらそんなことしなくてよくて
もし、同じx,yにいるならば間に白がいたらアウト
それ以外ならば、曲がる場所に白がいたらアウト
の二つを組み合わせる。一見、曲がる場所に白がいたら〜という条件は足りないように見えるけれど、
同じx,yにいるときのチェックでそこまで辿りつけるかをチェックしているのでセーフ
結果的にやるだけ。
#include <iostream> #include <cstdio> #include <iomanip> #include <vector> #include <map> #include <set> #include <queue> #include <bitset> #include <stack> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <cctype> #include <complex> #include <string> #include <sstream> using namespace std; #define all(c) c.begin(),c.end() #define rall(c) c.rbegin(),c.rend() #define rep(i,n) for(int i=0;i<(n);i++) #define tr(it,container) for(typeof(container.begin()) it = container.begin(); \ it != container.end(); ++it) #define mp(a,b) make_pair((a),(b)) #define eq == typedef long long ll; typedef complex<double> point; // up right down left const int dy[] = {-1,0,1,0}; const int dx[] = {0,1,0,-1}; const double EPS = 1e-9; const int days[] = {31,28,31,30,31,30,31,31,30,31,30,31}; const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31}; int main(){ int n,m; cin >> n >> m; vector<vector<char> > isBlack(n+2,vector<char>(m+2,false)); vector<pair<int,int> > BS; rep(i,n) rep(j,m){ char c; cin >> c; if(c == 'B'){ isBlack[i+1][j+1] = true; BS.push_back(make_pair(i+1,j+1)); } } int h = n+2,w = m+2; bool ok = true; for(int i=0;i<BS.size();i++){ for(int j=i+1;j<BS.size();j++){ int iy = BS[i].first; int ix = BS[i].second; int jy = BS[j].first; int jx = BS[j].second; if(ix == jx){ for(int k=iy;k<=jy;k++){ if(not isBlack[k][ix]){ ok = false; } } }else if(iy == jy){ for(int k=ix;k<=jx;k++){ if(not isBlack[iy][k]){ ok = false; } } }else{ if(not isBlack[iy][jx] and not isBlack[jy][ix]){ ok = false; } } } } cout << (ok?"YES":"NO") << endl; return 0; }