水灾（flood）

描述

这天 Robin 正打着游戏，正思考着怎么才能过关，突然，bong 的一声，家里的水管全爆了！！！

已知 Robin 的家可以用一个 n*m 的网格表示。

Robin 每秒钟可以走到上下左右 4 个方向的相邻格中的一个没有水的格子（他不喜欢踩水），而所有有水的格子每秒也会向四周的空格蔓延（上下左右四个格子）。显然最开始有水的格子是那些水管的位置。

Robin 家还有一些障碍格，比如他家的 60 英寸的大电视，比如一些紫檀木家具，还有墙也是一种障碍……，水跟 Robin 都不能进入这个格。当他到达地图边界时就可以认为他逃出了他家。

请问 Robin 怎么以最短的时间逃出家。

注意：

$\color{red}1.等 Robin 反应过来时已经过去了1秒。$

$\color{red}2.开始时，水可能不止一处。$

输入

第一行，两个整数 n 和 m，表示 Robin 家的行数跟列数。

接下来是一个 n*m 的字符串矩阵。其中，"."表示空地，水和 Robin 都能进去，"s"表示 Robin 所在位置，"w"表示爆掉的水管的位置，"#"表示障碍和墙， 水和 Robin 都不能进去。

输出

输入数据仅一行，能逃出去，则输出一个整数，表示 Robin 逃出家的最短时间。如果 Robin 出不去，则输出"IMPOSSIBLE"(不含引号)。

输入样例 1

4 4

####

#sw#

#..#

#..#

输出样例 1

3

输入样例 2

3 4

####

#s.#

#.w.

输出样例 2

IMPOSSIBLE

提示

【数据范围】

对于20%的数据，1<=n,m<=100；

对于100%的数据，1<=n,m<=1000。

本蒟的错解（内存超限）

#include<bits/stdc++.h>
using namespace std;
int n,m,step=1;
char a[1001][1001];
queue<int>sx,sy,wx,wy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='s')
				sx.push(i),sy.push(j);
			if(a[i][j]=='w')
				wx.push(i),wy.push(j);
		}
	while(!sx.empty())
	{
		for(int i=wx.size();i>=1;wx.pop(),wy.pop(),i--)
			for(int j=0;j<4;j++)
			{
				int xx=wx.front()+dx[j];
				int yy=wy.front()+dy[j];
				if(xx>0&&xx<=n&&yy>0&&yy<=m)
					if(a[xx][yy]!='w'&&a[xx][yy]!='#')
						wx.push(xx),wy.push(yy),a[xx][yy]='w';
			}
		for(int i=sx.size();i>=1;sx.pop(),sy.pop(),i--)
			for(int j=0;j<4;j++)
			{
				int xx=sx.front()+dx[j];
				int yy=sy.front()+dy[j];
				if(xx>0&&xx<=n&&yy>0&&yy<=m)
				{
					if(a[xx][yy]=='.')
						sx.push(xx),sy.push(yy);
				}
				else
				{
					printf("%d",step);
					return 0;	
				}
			}
		step++;
	}
	printf("IMPOSSIBLE");
	return 0;
}