/* Compete against Yourself. Author - Aryan (@aryanc403) */ /* Credits - Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder) Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder https://codeforces.com/contest/4/submission/150120627 */ #ifdef ARYANC403 #include <header.h> #else #pragma GCC optimize ("Ofast") //#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") #pragma GCC target ("sse,sse2,mmx") #pragma GCC optimize ("-ffloat-store") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define dbg(args...) 42; // #define endl "\n" #endif // y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } using namespace std; #define fo(i,n) for(i=0;i<(n);++i) #define repA(i,j,n) for(i=(j);i<=(n);++i) #define repD(i,j,n) for(i=(j);i>=(n);--i) #define all(x) begin(x), end(x) #define sz(x) ((lli)(x).size()) #define eb emplace_back #define X first #define Y second using lli = long long int; using mytype = long double; using ii = pair<lli,lli>; using vii = vector<ii>; using vi = vector<lli>; template <class T> using ordered_set = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; // X.find_by_order(k) return kth element. 0 indexed. // X.order_of_key(k) returns count of elements strictly less than k. // namespace Re = std::ranges; // namespace Ve = std::ranges::views; const auto start_time = std::chrono::high_resolution_clock::now(); void aryanc403() { auto end_time = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> diff = end_time-start_time; cerr<<"Time Taken : "<<diff.count()<<"\n"; } const lli INF = 0xFFFFFFFFFFFFFFFLL; const lli SEED=chrono::steady_clock::now().time_since_epoch().count(); mt19937_64 rng(SEED); inline lli rnd(lli l=0,lli r=INF) {return uniform_int_distribution<lli>(l,r)(rng);} class CMP {public: bool operator()(ii a , ii b) //For min priority_queue . { return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }}; void add( map<lli,lli> &m, lli x,lli cnt=1) { auto jt=m.find(x); if(jt==m.end()) m.insert({x,cnt}); else jt->Y+=cnt; } void del( map<lli,lli> &m, lli x,lli cnt=1) { auto jt=m.find(x); if(jt->Y<=cnt) m.erase(jt); else jt->Y-=cnt; } bool cmp(const ii &a,const ii &b) { return a.X<b.X||(a.X==b.X&&a.Y<b.Y); } using t4 = array<lli,4>; const vii dr = {{0,1},{-1,0},{0,-1},{1,0}}; const vector<t4> rot = { {1,0,0,1}, {0,-1,1,0}, {-1,0,0,-1}, {0,1,-1,0}, }; const lli MX = 207*207; bool visited[MX]; int main(void) { ios_base::sync_with_stdio(false);cin.tie(NULL); // freopen("txt.in", "r", stdin); // freopen("txt.out", "w", stdout); // cout<<std::fixed<<std::setprecision(35); // Ve::iota(1, 6) | Ve::transform([](int x) { return x * 2; }) | Ve::reverse | Ve::take(3) { lli R,C; cin>>R>>C; vector<string> a(R); for(auto &s:a) cin>>s; const lli N = R*C; vector<t4> dis(N); auto pre=[&]()->void{ lli s=-1; s=find(all(dr),ii{0,1})-dr.begin(); // dbg(s,dr[s]); assert(dr[s]==make_pair(0LL,1LL)); for(lli i=R-1;i>=0;i--) for(lli j=C-1;j>=0;j--){ if(a[i][j]=='#') dis[i*C+j][s]=-1; else{ if(j+1<C) dis[i*C+j][s]=1+dis[i*C+j+1][s]; } } s=find(all(dr),ii{0,-1})-dr.begin(); assert(dr[s]==make_pair(0LL,-1LL)); for(lli i=R-1;i>=0;i--) for(lli j=0;j<C;j++){ if(a[i][j]=='#') dis[i*C+j][s]=-1; else{ if(j>0) dis[i*C+j][s]=1+dis[i*C+j-1][s]; } } s=find(all(dr),ii{1,0})-dr.begin(); assert(dr[s]==make_pair(1LL,0LL)); for(lli j=0;j<C;j++) for(lli i=R-1;i>=0;i--){ if(a[i][j]=='#') dis[i*C+j][s]=-1; else{ if(i+1<R) dis[i*C+j][s]=1+dis[i*C+j+C][s]; } } s=find(all(dr),ii{-1,0})-dr.begin(); assert(dr[s]==make_pair(-1LL,0LL)); for(lli j=0;j<C;j++) for(lli i=0;i<R;i++){ if(a[i][j]=='#') dis[i*C+j][s]=-1; else{ if(i>0) dis[i*C+j][s]=1+dis[i*C+j-C][s]; } } }; pre(); lli curX=0,curY=0,curDr = 1,qurCnt = 0; #ifdef ARYANC403 const bool ask = false; #else const bool ask = true; #endif lli lstDist=-1; auto getDist = [&]()->lli{ if(ask){ lli d; cin>>d; lstDist=d; } else { lstDist=dis[curX*C+curY][curDr]; } return lstDist; }; auto moveLeft=[&]()->void{ qurCnt++; if(ask) cout<<"left"<<endl; else { curDr++; curDr%=4; // dbg("rot",curX,curY,curDr); } lstDist=getDist(); }; auto moveFwd=[&]()->void{ qurCnt++; // dbg(curX,curY,curDr,dr[curDr],lstDist); if(ask) cout<<"step"<<endl; else { curX+=dr[curDr].X; curY+=dr[curDr].Y; // dbg("move",curX,curY,curDr); assert(0<=curX&&curX<R); assert(0<=curY&&curY<C); assert(a[curX][curY]=='.'); } lstDist=getDist(); }; const t4 def = t4{-2,-2,-2,-2}; vector<t4> responses(MX,def); auto runDfs = [&]()->void{ responses.clear(); responses.resize(MX,def); memset(visited,0,sizeof(visited)); getDist(); lli cnt = 0; lli dire = 0,dxe=0,dye=0; y_combinator([&](const auto &self,const lli dx,const lli dy)->void{ cnt++; // dbg("currently at",dx,dy,dire,cnt,"|",curX,curY,curDr); const lli idx = (dx+102)*205+(dy+102); assert(!visited[idx]); visited[idx]=true; for(const auto &it:{0,1,2,3}){ const lli d=lstDist,curd=dire; responses[idx][dire]=d; // dbg(curX,curY,curDr,d); assert(d>=0); if(d){ const lli bx=dx+dr[dire].X,by=dy+dr[dire].Y; const lli ci = (bx+102)*205+(by+102); if(!visited[ci]){ dxe+=dr[dire].X; dye+=dr[dire].Y; moveFwd(); self(bx,by); } assert(dxe==dx&&dye==dy&&dire==curd); } moveLeft(); dire++; dire%=4; } if(dx||dy){ for(const lli &it:{0,1}){ moveLeft(); dire++; dire%=4; } dxe+=dr[dire].X; dye+=dr[dire].Y; moveFwd(); for(const lli &it:{0,1}){ moveLeft(); dire++; dire%=4; } } // dbg("returning at",dx,dy); })(0LL,0LL); qurCnt++; // cerr<<qurCnt<<endl; assert(qurCnt<=100000); }; runDfs(); const auto juryResponse = responses; lli juryVisitedCells = 0; for(const auto &v:juryResponse){ bool gl=false; for(const auto &x:v) if(x>=0) gl=true; if(gl) juryVisitedCells++; } auto runDfs2 = [&](const lli sx,const lli sy,const lli sd)->bool{ // dbg("runDfs2",sx,sy,sd); memset(visited,0,sizeof(visited)); bool isValid = true; lli curVisited = 0; y_combinator([&](const auto &self,const lli dx,const lli dy)->void{ if(!isValid) return; const lli idx = (dx+102)*205+(dy+102); assert(!visited[idx]); visited[idx]=true; curVisited++; for(const auto &it:{0,1,2,3}){ const lli ogX=sx+rot[sd][0]*dx+rot[sd][1]*dy; const lli ogY=sy+rot[sd][2]*dx+rot[sd][3]*dy; assert(0<=ogX&&ogX<R); assert(0<=ogY&&ogY<C); const lli d=dis[ogX*C+ogY][(it+sd+16)%4]; if(d!=juryResponse[idx][it]){ isValid=false; break; } assert(d>=0); if(d){ const lli bx=dx+dr[it].X,by=dy+dr[it].Y; const lli ci = (bx+102)*205+(by+102); if(!visited[ci]) self(bx,by); } } })(0LL,0LL); if(curVisited!=juryVisitedCells) isValid=false; return isValid; }; set<ii> validRes; auto mockRun=[&](const lli i,const lli j,const lli d)->void{ if(sz(validRes)>=2) return; if(validRes.count(ii{i,j})) return; if(runDfs2(i,j,d)) validRes.insert(ii{i,j}); }; for(lli i=0;i<R;i++) for(lli j=0;j<C;j++) for(lli d=0;d<4;d++){ if(a[i][j]=='.') mockRun(i,j,d); } dbg(validRes); if(sz(validRes)==1){ const auto p=*validRes.begin(); cout<<"yes "<<p.X+1<<" "<<p.Y+1<<endl; } else { assert(sz(validRes)>=2); cout<<"no"<<endl; } } aryanc403(); return 0; }