#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace { using Integer = long long; //__int128; template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const vector& vec){for(int i=0; i ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template void print(const H& head){ cout << head; } template void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); } template void println(const T& ... values){ print(values...); cout << endl; } template void eprint(const H& head){ cerr << head; } template void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); } template void eprintln(const T& ... values){ eprint(values...); cerr << endl; } string operator "" _s (const char* str, size_t size){ return move(string(str)); } constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);} constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);} constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); } inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed mt19937 mt(chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()); template string join(const vector& v, const string& sep){ stringstream ss; for(int i=0; i0) ss << sep; ss << v[i]; } return ss.str(); } } constexpr long long mod = 9_ten + 7; int main(){ int h,w; cin >> h,w; vector v(h); cin >> v; int s,t; for(int i=0; i dist(2*h*w, 1145148931919LL); dist[s<<1] = 0; queue q; q.push( s<<1 ); int dx[] = {+1,+1,-1,-1,+2,+2,-2,-2, +1,+1,-1,-1}; int dy[] = {+2,-2,+2,-2,+1,-1,+1,-1, +1,-1,+1,-1}; while(q.size()){ auto p = q.front(); q.pop(); for(int k= ((p&1)?8:0); k<((p&1)?12:8); k++){ int xx = (p>>1)%w + dx[k]; int yy = (p>>1)/w + dy[k]; if(xx<0 || xx>=w || yy<0 || yy>=h) continue; int next = (xx + yy*w) << 1; next |= p&1; if(v[yy][xx] == 'R') next ^= 1; if(dist[next] >= 1145148931919LL){ dist[next] = dist[p] + 1; q.push(next); } } } long long ans = min(dist[t<<1], dist[(t<<1)|1]); println( ans == 1145148931919LL ? -1 : ans); return 0; }