#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 cnt = 0; vector A(N); REP(i,N) { cin>>A[i]; // 通過可能なボタンの総数を数えておく REP(j,M) if (A[i][j] == '.') ++cnt; } // sample 3 より最大一回は右に曲がってよいとしたとき、サイクルができればよさそう。 // 以下の条件があるので計算量を落とせる // * 右に曲がれるのはスタート地点のみ。スタート地点毎に計算をすれば左 or 真っ直ぐにしか進めないとみなせる // * 左に曲がるとその先はもう進めなくなるので、それ以上すすめなくなるまで真っ直ぐ進む。 // O(N^2*M^2) const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; // O(N*M) int sx, sy; function search = [&](int x, int y, int d, int c) { for (int dd = 0; dd >= -1; --dd) { 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; return false; } // 進めないなら左へ if (A[ny][nx] != '.') continue; A[ny][nx] = '@'; // 通過フラグを立てておく bool found = search(nx,ny,nd,c+1); A[ny][nx] = '.'; if (found) return true; // まっすぐか左かしか移動しないので break する break; } return false; }; // O(N^2*M^2) REP(d, 4) { REP(y,N) REP(x,M) { if (A[y][x] != '.') continue; sx = x; sy = y; A[sy][sx] = '@'; if (search(sx,sy,d,1)) { cout<<"YES"<solve(); delete obj; return 0; } #endif