#include #include #include #include #include #include #include #include #include using namespace std; 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){ 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+yy*m == start){ return ret; } //今いる場所から左に曲がる int next_x = pos%m + x[(toward+3)%4]; int next_y = pos/m + y[(toward+3)%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+3)%4); }else{ //進めないならおしまい //次でstart地点に戻っていれば終了 if(next == start) return ret; //そうでなければ不適切 else return -1; } } int main(){ int n,m; cin >> n >> m; vector v(n); for(int i=0; i> v[i]; } //ごめんなさい cout << "YES" << endl; return 0; 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; for(int i=0; i