#ifdef DEBUG #define _GLIBCXX_DEBUG #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define CERR( MESSAGE ) cerr << MESSAGE << endl; #define COUT( ANSWER ) cout << ANSWER << endl #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define CERR( MESSAGE ) #define COUT( ANSWER ) cout << ANSWER << "\n" #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #endif #include using namespace std; using ll = long long; #define MAIN main #define TYPE_OF( VAR ) decay_t #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define QUIT return 0 #define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } #endif #define DIJKSTRA_BODY( INITIALISE_PREV , SET_PREV ) \ static const U& unit = Unit(); \ assert( unit != m_found && unit < m_infty ); \ U weight[size_max]; \ \ for( int i = 0 ; i < m_size ; i++ ){ \ \ weight[i] = m_infty; \ \ } \ \ set > vertex{}; \ const int i_start = e_inv( t_start ); \ const int i_final = e_inv( t_final ); \ vertex.insert( pair( weight[i_start] = unit , i_start ) ); \ INITIALISE_PREV; \ \ while( ! vertex.empty() ){ \ \ auto itr_vertex = vertex.begin(); \ const pair v = *itr_vertex; \ const int& i = v.second; \ \ if( i == i_final ){ \ \ break; \ \ } \ \ const U& u = v.first; \ weight[i] = m_found; \ vertex.erase( itr_vertex ); \ const list > edge_i = E( e( i ) ); \ list > changed_vertex{}; \ \ for( auto itr_edge_i = edge_i.begin() , end_edge_i = edge_i.end() ; itr_edge_i != end_edge_i ; itr_edge_i++ ){ \ \ const int& j = e_inv( itr_edge_i->first ); \ U& weight_j = weight[j]; \ \ if( weight_j != m_found ){ \ \ const U& edge_ij = itr_edge_i->second; \ const U temp = Addition( u , edge_ij ); \ assert( edge_ij != m_found && temp != m_found && !( temp < edge_ij ) && temp < m_infty ); \ \ if( weight_j > temp ){ \ \ if( weight_j != m_infty ){ \ \ vertex.erase( pair( weight_j , j ) ); \ \ } \ \ SET_PREV; \ changed_vertex.push_back( pair( weight_j = temp , j ) ); \ \ } \ \ } \ \ } \ \ for( auto itr_changed = changed_vertex.begin() , end_changed = changed_vertex.end() ; itr_changed != end_changed ; itr_changed++ ){ \ \ vertex.insert( *itr_changed ); \ \ } \ \ } \ // メモリが不足する場合はEの定義を前計算しないでその都度計算させること。 template > E(const T&) , int size_max> class DijkstraBody { private: int m_size; U m_infty; U m_found; int m_length; map m_memory; vector m_memory_inv; public: inline DijkstraBody( const int& size , const U& infty , const U& found ); // 経路が存在しない場合の返り値はm_infty U Solve( const T& t_start , const T& t_final ); U Solve( const T& t_start , const T& t_final , list& path ); const U& Infty() const; private: virtual const U& Unit() const = 0; virtual U Addition( const U& , const U& ) const = 0; virtual T e( const int& i ); virtual int e_inv( const T& t ); virtual void Reset(); }; // 入力の範囲内で要件 // (1) Eの値の各成分の第2成分が0以上である。 // (2) 2^{31}-1がEの値の各成分の第2成分size_max個以下の和で表せるいかなる数よりも大きい。 // (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。 // が成り立つ場合にのみサポート。 // O((size+|E|)log size)で単一始点最短経路探索。 template > E(const int&) , int size_max> class Dijkstra : public DijkstraBody { public: inline Dijkstra( const int& size ); private: inline const ll& Unit() const; inline ll Addition( const ll& , const ll& ) const; inline int e( const int& i ); inline int e_inv( const int& t ); inline void Reset(); }; // 入力の範囲内で要件 // (1) Eの値の各成分の第2成分がe_T()以上である。 // (2) inftyがEの値の各成分の第2成分size_max個以下の和で表せるいかなる項よりも大きい。 // (3) foundがEの値の各成分の第2成分size_max個以下の和で表せず、inftyとも異なる。 // (4) (U,m_U:U^2->U,e_U:1->U)がbool operator<(const U&,const U&)に関して順序モノイドである。 // (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。 // が成り立つ場合にのみサポート。 // O((size+|E|)(log size)^2)で単一始点最短経路探索。 template > E(const T&) , int size_max> class MemorisationDijkstra : public DijkstraBody { public: inline MemorisationDijkstra( const int& size , const U& infty = 9223372036854775807 , const U& found = -1 ); private: inline const U& Unit() const; inline U Addition( const U& , const U& ) const; }; // 入力の範囲内で要件 // (1) Eの値の各成分の第2成分がe_T()以上である。 // (2) inftyがEの値の各成分の第2成分size_max個以下の和で表せるいかなる項よりも大きい。 // (3) foundがEの値の各成分の第2成分size_max個以下の和で表せず、inftyとも異なる。 // (4) (U,m_U:U^2->U,e_U:1->U)がbool operator<(const U&,const U&)に関して順序モノイドである。 // (5) (enum_T,enum_T_inv)が互いに逆写像である。 // (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。 // が成り立つ場合にのみサポート。 // O((size+|E|)log size)で単一始点最短経路探索。 template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> class EnumerationDijkstra : public DijkstraBody { public: inline EnumerationDijkstra( const int& size , const U& infty = 9223372036854775807 , const U& found = -1 ); private: inline const U& Unit() const; inline U Addition( const U& , const U& ) const; inline T e( const int& i ); inline int e_inv( const T& t ); inline void Reset(); }; template > E(const T&) , int size_max> inline DijkstraBody::DijkstraBody( const int& size , const U& infty , const U& found ) : m_size( size ) , m_infty( infty ) , m_found( found ) , m_length() , m_memory() , m_memory_inv() { static_assert( ! is_same::value ); } template > E(const int&) , int size_max> inline Dijkstra::Dijkstra( const int& size ) : DijkstraBody( size , 9223372036854775807 , -1 ) {} template > E(const T&) , int size_max> inline MemorisationDijkstra::MemorisationDijkstra( const int& size , const U& infty , const U& found ) : DijkstraBody( size , infty , found ) {} template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline EnumerationDijkstra::EnumerationDijkstra( const int& size , const U& infty , const U& found ) : DijkstraBody( size , infty , found ) {} template > E(const T&) , int size_max> U DijkstraBody::Solve( const T& t_start , const T& t_final ) { DIJKSTRA_BODY( , ); Reset(); return weight[i_final]; } template > E(const T&) , int size_max> U DijkstraBody::Solve( const T& t_start , const T& t_final , list& path ) { DIJKSTRA_BODY( T prev[size_max] = {} , prev[j] = i ); int i = i_final; while( i != i_start ){ path.push_front( e( i ) ); i = prev[i]; } path.push_front( t_start ); Reset(); return weight[i_final]; } template > E(const T&) , int size_max> const U& DijkstraBody::Infty() const { return m_infty; } template > E(const int&) , int size_max> inline const ll& Dijkstra::Unit() const { static const ll unit = 0; return unit; } template > E(const T&) , int size_max> inline const U& MemorisationDijkstra::Unit() const { return e_U(); } template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline const U& EnumerationDijkstra::Unit() const { return e_U(); } template > E(const int&) , int size_max> inline ll Dijkstra::Addition( const ll& u0 , const ll& u1 ) const { return u0 + u1; } template > E(const T&) , int size_max> inline U MemorisationDijkstra::Addition( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); } template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline U EnumerationDijkstra::Addition( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); } template > E(const T&) , int size_max> T DijkstraBody::e( const int& i ) { assert( i < m_length ); return m_memory_inv[i]; } template > E(const int&) , int size_max> inline int Dijkstra::e( const int& i ) { return i; } template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline T EnumerationDijkstra::e( const int& i ) { return enum_T( i ); } template > E(const T&) , int size_max> int DijkstraBody::e_inv( const T& t ) { if( m_memory.count( t ) == 0 ){ assert( m_length < m_size ); m_memory_inv.push_back( t ); return m_memory[t] = m_length++; } return m_memory[t]; } template > E(const int&) , int size_max> inline int Dijkstra::e_inv( const int& t ) { return t; } template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline int EnumerationDijkstra::e_inv( const T& t ) { return enum_T_inv( t ); } template > E(const T&) , int size_max> void DijkstraBody::Reset() { m_length = 0; m_memory.clear(); m_memory_inv.clear(); return; } template > E(const int&) , int size_max> inline void Dijkstra::Reset() {} template > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline void EnumerationDijkstra::Reset() {} inline DEXPR( int , bound_H , 500 , 10 ); inline CEXPR( int , bound_W , bound_H ); static_assert( ll( bound_H ) * bound_W < ll( 1 ) << 31 ); inline CEXPR( int , bound_HW , bound_H * bound_W ); int H , W , H_minus , W_minus , HW; inline pair EnumHW( const int& v ) { return { v / W , v % W }; } inline int EnumHW_inv( const int& h , const int& w ) { return h * W + w; } inline void SetEdgeOnGrid( const string& Si , const int& i , list > > ( &e )[bound_HW] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){int v = EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back({v,{0,1}});}if(i+10){e[EnumHW_inv(i,j-1)].push_back({v,{1,0}});}if(j+1k?0:jh?3:(assert(false),-1);} inline int DirectionNumberOnGrid( const int& v , const int& w ){auto [i,j]=EnumHW(v);auto [k,h]=EnumHW(w);return DirectionNumberOnGrid(i,j,k,h);} inline int ReverseDirectionNumberOnGrid( const int& n ){assert(0<=n&&n<4);return(n+2)%4;} list > > e[bound_HW]; inline list > > E( const int& v ) { return e[v]; } inline pair add( const pair& t0 , const pair& t1 ) { return { t0.first + t1.first , t0.second + t1.second }; } inline const pair& zero() { static const pair z{}; return z; } inline int id( const int& v ) { return v; } int MAIN() { UNTIE; SET_ASSERT( H , 2 , bound_H ); SET_ASSERT( W , 2 , bound_W ); H_minus = H - 1; W_minus = W - 1; HW = H * W; assert( HW <= bound_HW ); FOR( i , 0 , H ){ CIN( string , Si ); SetEdgeOnGrid( Si , i , e ); } EnumerationDijkstra,add,zero,E,bound_HW,id,id> dijkstra{ HW , { HW , HW } , { -1 , -1 } }; auto [X,Y] = dijkstra.Solve( EnumHW_inv( 0 , 0 ) , EnumHW_inv( H_minus , W_minus ) ); if( X == HW ){ RETURN( "No" ); } COUT( "Yes" ); COUT( X << " " << Y ); QUIT; }