#include #define PII pair using namespace std; const int N=505,INF=0x3f3f3f3f; int h,w; char s[N][N]; int d[N][N][2]; int sx,sy,gx,gy; int dx8[8]={2,2,1,1,-1,-1,-2,-2},dy8[8]={1,-1,2,-2,2,-2,1,-1}; int dx4[4]={1,1,-1,-1},dy4[4]={1,-1,-1,1}; int bfs(){ queue>que; for(int i=0;i=h||ny<0||ny>=w)continue; if(d[nx][ny][nm]!=INF)continue; que.push(make_pair(nm,PII(nx,ny))); d[nx][ny][nm]=d[p.first][p.second][node]+1; } } else{ for(int i=0;i<4;i++){ int nx=p.first+dx4[i],ny=p.second+dy4[i]; int nm=node^(s[nx][ny]=='R'); if(nx<0||nx>=h||ny<0||ny>=w)continue; if(d[nx][ny][nm]!=INF)continue; que.push(make_pair(nm,PII(nx,ny))); d[nx][ny][nm]=d[p.first][p.second][node]+1; } } } return min(d[gx][gy][0],d[gx][gy][1]); } int main(){ //freopen("knight.in","r",stdin); //freopen("knight.out","w",stdout); cin>>h>>w; for(int i=0;i>str; for(int j=0;j