#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; } // // 左に曲がる回数は以下のようなケースで最大 6 回まで // // ++++++++ +++ // + + + + // + S++ + // + + // ++++++++++++ // // 閉路に含まれるマス数は 4*(N+M) 以下なのでそれ以上なら return // よって閉路探索時間と '.' 総数は K = 4*(N+M) 以下となる。 if (cnt > 4*(N+M)) { cout<<"NO"< 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