HZNUOJ

曾大浪的连连看

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:65     AC:15     Score:99.12

Description

在《连连看》游戏中只要将相同的两个方块,用三根以内的直线连在一起就可以消除,其中的线不能穿过其他的方块,规则简单容易上手。

因为曾小浪被吐槽了,所以换了曾小浪的哥哥曾大浪作为故事主人公。

曾大浪最近沉迷游戏《连连看》不能自拔,渐渐地他也成为了连连看高手。但是最近他发现随着自己年龄的增长,自己的思考速度慢慢的已经跟不上自己的手速了,因此他迫切的需要一款辅助软件帮助他提升自己的水平。

在游戏中,曾大浪可以快速的点击屏幕,选中零个,一个或者多个方块,但是由于思考速率有限,他需要你们来帮他判断他选中的位置是否可以消除方块。题目将会给出当前的游戏状态,其中最左上角的位置记作(1,1),代表第1行第1个位置。其中'.'代表该位置为空,其余字符代表当前位置的方块形态。

接下来会给出曾大浪的点击位置(x1,y1)与(x2,y2)分别代表曾大浪第一次点击的是第x1行的第y1个位置,第二次点击的是第x2行的第y2个位置。请根据游戏状态判断是否可以消除方块,如果可以,请给年迈的曾大浪绘制出合理的路径。

曾大浪对路径非常的挑剔。因此提出以下几个要求:

1.路径尽可能少的转弯

2.需要两条直线时,使拐弯的点的x坐标尽可能的小

3.需要三条直线时,优先选择两横一竖的路径形态,并且使竖线尽可能靠近左边。次选两束一横的路径形态,并且使横线尽可能靠上。

如果不存在这样的路径,请输出“no way!”。


详细图片见下方hint

Input

输入的第一行包括两个整数n,m(1<=n,m<=100)

接下来有n行,每行包括m个字符,代表连连看的原始状态

接下来有四个正整数x1,y1,x2,y2,其中(x1,y1),(x2,y2)分别代表曾大浪第一次点击的是第x1行的第y1个位置,第二次点击的是第x2行的第y2个位置。

题目保证点击位置不会超出范围。

Output

如果可以消除方块,由于路径输出问题,请将原图形扩展成(n+2)*(m+2)的图形(周围用符号'.'扩充)之后再绘制出合理的路径。

如果不可以消除方块,请输出"no way!"

Samples

input
3 3 123 ... 123 1 1 3 1
output
..... .*23. .*... .*23. .....
input
3 3 1.3 ... .12 1 1 3 2
output
..... .**3. ..*.. ..*2. .....
input
4 4 1..3 .... .... 3..1 1 1 4 4
output
...... .**.3. ..*... ..*... .3***. ......
input
3 3 123 222 123 1 1 3 1
output
..... **23. *222. **23. .....
input
2 2 12 .. 1 1 2 2
output
no way!

Hint



样例一两点直线连接不拐弯 
 
下图样例二,点击(1,1),(3,2)存在多条连接路径,但是选择拐弯最少的,且拐点x坐标最小的 
如下图 

下图样例三,点击(1,1),(4,4)存在多条连接路径,但优先选择两横一竖形态的路径,并且使得竖线尽可能靠近左边 
如下图 


Author

YU, Deli