问题 4399 --2010-网络赛G-靠墙走

4399: 2010-网络赛G-靠墙走

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

为什么我们要靠墙走呢,锴哥说因为我们要偷偷摸摸的走,然后这个问题就出现了。

假定我们的迷宫存在于一个平面上,拥有唯一的出发点'S'和唯一的终点'E',并且'S''E'只出现在迷宫的边缘;此外迷宫中的墙用'#'表示,可以行走的路由'.'表示;迷宫除出入口之外完全封闭;'S''E'之间至少会间隔一个墙面距离。

每组测试数据将首先于第一行给出正整数wh,表示迷宫的尺寸为宽w,高h;接下来数行将给出一个该尺寸的迷宫地图。

现在,我们的目标是计算按照一定的规则从'S'行走到'E'所用的步数。这样的规则有两个:总是靠着左边的墙面走;总是靠着右边的墙面走。

数据将保证按照规则行走一定能从'S'到达'E'

输入

首先第一行给出一个整数t,代表将有t组测试数据。

对于每组测试数据,首先在一行给出w,h(3 <= w, h <= 40),

接下来将给出h行字符串,每行字符串的长度皆为w,代表这个迷宫的平面图。

输出

对于每组测试数据,在一行内输出两个整数,从左往右分别为:总是靠左边墙面走所需步数;总是靠右边墙面走所需步数。

样例输入

2<br/>8 8<br/>########<br/>#......#<br/>#.####.#<br/>#.####.#<br/>#.####.#<br/>#.####.#<br/>#...#..#<br/>#S#E####<br/>9 5<br/>#########<br/>#.#.#.#.#<br/>S.......E<br/>#.#.#.#.#<br/>#########<br/>

样例输出

37 5 <br/>17 17 <br/>

提示

 

来源

[提交][状态]