Description

zbj作为一个热(xiang)爱(dang)学(xian)习(yu)的好同学，每天都在掰着手指头等周末。
今天终于到了周五，等到下午六点他就又可以在寝室做两天咸鱼了。但是zbj上午上完课把钥匙丢在了教室，被wjw捡到了，所以他必须先去wjw手里取得钥匙才能回寝室。
于是机智的wjw为了方便zbj拿钥匙，他去配了好多把zbj的钥匙，分别放在不同的地方 (厉害了小老弟)。
现在zbj想要尽快的回到寝室中，他需要取得任意一把钥匙才能够回寝室，请你帮他计算出回寝室的最短路程。
学校可以被看做是一个n * m的网格，其中一些路有障碍，钥匙和家所在的地方也可以看做是道路，可以通过。zbj可以在任意一条道路中选择上下左右四个方向移动，一次移动算作一步。

Input

多组数据，T<=50,对于每组数据有:
第一行有两个整数n,m。
接下去n行每行m个字符，代表学校地图。
其中, '.'表示道路，'#'表示障碍物，'L' 表示zbj所在的位置,'W'表示钥匙的位置，'Q'表示寝室的位置。题目保证最少有一条路可以拿到钥匙并且回到寝室。

Output

zbj回寝室需要走的最少步数。

Sample Input

8 10
W....#.#W#
..#..#...#
...Q##.#.#
##........
..##.#..##
..........
##..#...##
###..L....

Sample Output

17

解析：因为W有多个，如果我们先求L到每个W的最短路，再求每个W到Q的最短路，那么肯定就超时了，其实我们转化为BFS求L到每个W的距离和Q到每个W的距离，相加就是L到某个W再到Q的最短距离。

注意点：题目中没有指出n，m的范围，经过测试应该是2000。

#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
vector ys;
const int N=2005;
char a[N][N];
int n,m,qx,qy,zx,zy,dist[3][N][N];
//dist[1][][]记录L到每个点的距离，dist[2][][]记录Q到每个点距离
void solve(int x,int y,int id)
{queue q;q.push({x,y});dist[id][x][y]=0;int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};while(q.size()){int x1=q.front().first;int y1=q.front().second;q.pop();for(int i=0;i<4;i++){int x2=x1+dx[i],y2=y1+dy[i];if(x2>=1&&x2<=n&&y2>=1&&y2<=m&&a[x2][y2]!='#'&&dist[id][x2][y2]==-1){	dist[id][x2][y2]=dist[id][x1][y1]+1;q.push({x2,y2});}}}
}
int main()
{while(~scanf("%d%d",&n,&m)){memset(dist,-1,sizeof dist);//初始化距离数组ys.erase(ys.begin(),ys.end());//清空存贮W的坐标for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf(" %c",&a[i][j]);if(a[i][j]=='W') ys.push_back({i,j});//W，存入ys中else if(a[i][j]=='L') qx=i,qy=j;//起点Lelse if(a[i][j]=='Q') zx=i,zy=j;//终点Q}}solve(qx,qy,1);solve(zx,zy,2);int minn=0x3f3f3f3f;for(int i=0;i