#include #include #include #include #include #include #include #include #include using namespace std; //l b r u int x[] = {-1,0,1,0}; int y[] = {0,1,0,-1}; int dfs(vector > &G, vector &visit, int pos){ visit[pos] = true; int ret = 1; for(int i=0; i &G, int n, int m, vector &visit, int pos, int start, int toward, bool right){ visit[pos] = true; int ret = 1; //進めるだけ進む //すでに訪れた点にぶつかるとそこで止まる。 int xx = pos%m + x[toward]; int yy = pos/m + y[toward]; while(xx>=0 && xx < m && yy>=0 && yy < n){ if(G[yy][xx]=='.' && !visit[xx+yy*m]){ pos = xx + yy*m; visit[pos] = true; ret++; xx = pos%m + x[toward]; yy = pos/m + y[toward]; }else{ break; } } //次がstart地点なら終了 if(xx>=0 && xx < m && yy>=0 && yy < n && xx+yy*m == start){ return ret; } //今いる場所から左に曲がる int next_x = pos%m + x[(toward+1)%4]; int next_y = pos/m + y[(toward+1)%4]; int next = next_x + next_y*m; //曲がった先の場所に進めるなら進む if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && !visit[next] && G[next_y][next_x]=='.' ){ return ret + dfs_(G,n,m,visit, next, start, (toward+1)%4, right); }else{ //次でstart地点に戻っていれば終了 if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){ return ret; } } //右に1回だけ曲がれる if(right==false){ right = true; next_x = pos%m + x[(toward+3)%4]; next_y = pos/m + y[(toward+3)%4]; next = next_x + next_y*m; //曲がった先の場所に進めるなら進む if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && !visit[next] && G[next_y][next_x]=='.' ){ return ret + dfs_(G,n,m,visit, next, start, (toward+3)%4, right); }else{ //次でstart地点に戻っていれば終了 if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){ return ret; } } } //start地点に戻っていないのに行く先がなかったら不適切 return -1; } int main(){ int n,m; cin >> n >> m; vector v(n); for(int i=0; i> v[i]; } vector > G(n*m); vector s; for(int i=0; i= m || yy<0 || yy >= n) continue; if(v[yy][xx] == '.'){ G[m*i + j].push_back(yy*m + xx); } } } } } vector visit(n*m, false); bool valid = dfs(G, visit, s[0]) == s.size(); if(valid == false){ cout << "NO" << endl; return 0; } valid = false; //最初に追加された点は必ず角になるので探索は1回で十分 for(int i=0; i<1 && valid == false; i++){ int start = s[i]; int start_x = s[i]%m; int start_y = s[i]/m; for(int j=0; j<4 && valid == false; j++){ fill(visit.begin(), visit.end(), false); int cnt = dfs_(v, n, m, visit, start, start, j, false); valid |= cnt == s.size(); } } cout << (valid?"YES":"NO") << endl; return 0; }