OI题库

题1  神奇的风

【问题描述】

T博士最近在研究一种神奇的风。

这种风有一个源头，称之为“风口”。风口的风要么是顺时针的，要么是逆时针的。

这种风是有能量的。

这种风是能传播的，如果风口周围都能传播风，风会像这样产生下一级的风：

 

产生的下一级风的能量依据新产生的风所在的地形决定，有两种可以传递这种风的地形：

一、平地，下一级风的能量与风口的风能量相等，这种地形用“.”表示。

二、少量障碍物，下一级风的能量是风口的风能量的一半，这种地形用“*”表示。

每个新产生的风都能作为新的风口继续产生下一级风。

此外，还有一种地形是不能传递风的：大量障碍物，用“#”表示。

如果在风口的某一方向是“#”地形，则该方向不会产生下一级风，其他方向视该位置的地形而定，就是说，如果是“.”或“*”地形则该方向照样传播。

T博士还发现了这种神奇的风的叠加规则：两股风叠加时，无论它们的转向是否相同，都只保留能量较大的那股风，即风叠加后的能量和转向都与叠加前能量较大的那股风相同。而如果叠加的两股风的能量相同且转向相同，则保留其中任意一股。两股风能量相同且转向不同时叠加的情况未知，因为T博士至今还没碰到这样的情况。

T博士画了几张地图，他想知道地图上的某点风的转向和能量。

【输入格式】

输入文件wind.in的第一行是两个整数m和n，表示地图大小为m行n列。

接下来的m行，每行是n个字符，只会是以下的几种：

“S”表示风口，保证图中有且仅有一个“S”。

“E”表示目的地，即T博士想知道的那个点。

“.”“*”“#”见描述。

第m+2行是一个整数“0”或“1”，分别表示风口的风是顺时针方向或逆时针方向。

约定“S”处的风能量为16384，“S”和“E”处的地形均为平地。

【输出格式】

    输出文件为wind.out。

若目的地会有风传到，则输出两行：第一行为一个整数，为目的地的风的能量；第二行为一个整数“0”或“1”，表示意义同输入格式。此种情形下保证目的地的风的能量大于0。

若目的地没有风传到，则输出一行：“There’s no wind!”（双引号内的字符，全英文标点）。

【样例输入1】

3 4

####

S**E

####

0

【样例输出1】

4096  （传递过程中经过两个“*”地形，能量变为原来的1/4，即变为4096）

1     （E处的风是逆时针的）

【样例输入2】

2 4

....

S**E

0

【样例输出2】

16384（传到目的地的风能量最大的为16384）

1（E处的风是逆时针的）

【样例输入3】

6 8

********

********

***S****

###*....

...#....

E..#....

1

【样例输出3】

There’s no wind!

【数据范围】

对于20%的数据，m,n均不超过10。

对于50%的数据，m,n均不超过100。

对于100%的数据，m,n均不超过200。

【提示】

不要问我单引号怎么输出。