#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int maxn=520;const int inf=0x3f3f3f3f;int dx[5]= {0,-1,1,0,0 };int dy[5]= {0,0,0,-1,1 };char mp[maxn][maxn];int map[maxn][maxn];int mx[maxn],my[maxn];int dis[maxn][maxn];bool vis[maxn][maxn];int stx,sty,edx,edy,ind;int n,m;struct node{ int x,y,st;};bool bianjie(node nod){ if(vis[nod.x][nod.y]==0 && map[nod.x][nod.y]>=0 && nod.x<n && nod.y<m && nod.x>=0 && nod.y>=0) return 1; return 0;}void bfs(int u){ node tmp; queue<node>que; memset(vis,0,sizeof(vis)); tmp.x=mx[u],tmp.y=my[u],tmp.st=0; vis[mx[u]][my[u]]=1,que.push(tmp); while(!que.empty()) { node now=que.front(); que.pop(); for(int i=0; i<=ind; i++) if(now.x==mx[i] && now.y==my[i]) dis[u][i]=min(dis[u][i],now.st); int dir=map[now.x][now.y]; if(dir>0) { tmp=now; tmp.x+=dx[dir]; tmp.y+=dy[dir]; tmp.st++; if(bianjie(tmp)) vis[tmp.x][tmp.y]=1, que.push(tmp); } else if (dir==0) { for (int i=1; i<5; i++) { tmp.x=now.x+dx[i]; tmp.y=now.y+dy[i]; tmp.st=now.st+1; if (bianjie(tmp)) { vis[tmp.x][tmp.y]=1; que.push(tmp); } } } }}void initbfs(){ memset(dis,inf,sizeof(dis)); for(int i=0; i<=ind; i++) bfs(i);}int dp[1<<11][12];int getone(int xa){ int cnt=0; while (xa) cnt++,xa&=xa-1; return cnt;}void solve(){ memset(dp,0x3f,sizeof(dp)),dp[1][0]=0; int lim=1<<ind,res=1,ans=inf; for (int i=1;i<lim;i++) for (int j=0;j<ind;j++) { if (i&(1<<j)) { int sy=i^(1<<j); for (int k=0;k<ind;k++) if (sy&(1<<k)) dp[i][j]=min(dp[i][j],dp[sy][k]+dis[k][j]+2); } int dn=getone(i); int dt=dp[i][j]+dis[j][ind]; if (dt>=inf) continue; if (dn>res) res=dn,ans=dt; else if (dn==res) ans=min(ans,dt); } if (ans>=inf) ans=-1; printf("%dn",ans);}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { ind=0; for(int i=0; i<n; i++) { scanf("%s",mp[i]); for(int j=0; j<m; j++) { if(mp[i][j]=='W' || mp[i][j]=='#') map[i][j]=-1; else if(mp[i][j]=='U') map[i][j]=1; else if(mp[i][j]=='D') map[i][j]=2; else if(mp[i][j]=='L') map[i][j]=3; else if(mp[i][j]=='R') map[i][j]=4; else if(mp[i][j]=='0') map[i][j]=0; else if(mp[i][j]=='$') mx[++ind]=i,my[ind]=j,map[i][j]=0; } } scanf("%d%d%d%d",&stx,&sty,&edx,&edy); mx[0]=--stx,my[0]=--sty; mx[++ind]=--edx,my[ind]=--edy; initbfs(); solve(); }}
