#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class TvZapping2 { public: void solve(void) { int N,M; cin>>N>>M; int sx,sy, cnt; sx = sy = -1; cnt = 0; vector A(N); REP(i,N) { cin>>A[i]; // 通過可能なボタンの総数を数えておく REP(j,M) if (A[i][j] == '.') ++cnt; // 押せるボタンの位置どれか一つを取得しておく if (sx < 0) { REP(j,M) if (A[i][j] == '.') { sx = j; sy = i; break; } } } // sample 3 より最大一回は右に曲がってよいとしたとき、サイクルができればよさそう。 vector> vis(N,vector(M,false)); const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; // O(N*M) function rec = [&](int x, int y, int d, int r, int c) { for (int dd = -1; dd <= 1; ++dd) { // 右にすでに一回まがっていたらもう曲がれない if (dd==1 && r==1) break; int nd = (4+d+dd)%4; int nx = x+dx[nd]; int ny = y+dy[nd]; if (nx < 0 || M <= nx || ny < 0 || N <= ny) continue; if (nx==sx && ny==sy) { if (cnt == c) return true; continue; } if (A[ny][nx]!='.') continue; if (vis[ny][nx]) continue; vis[ny][nx] = true; if (rec(nx,ny,nd,(dd==1),c+1)) return true; vis[ny][nx] = false; } return false; }; REP(d, 4) { vis[sy][sx] = true; if (rec(sx,sy,d,0,1)) { cout<<"YES"<solve(); delete obj; return 0; } #endif