问题 2743 --P1143 飘飘乎居士的约会

2743: P1143 飘飘乎居士的约会

题目描述

  又是美妙的一天,这天飘飘乎居士要和MM约会,因此他打扮的格外帅气。但是,因为打扮的时间花了太久,离约会的时间已经所剩无几。幸运的是,现在飘飘乎居士得到了一张n*m的地图,图中左上角是飘飘乎居士的位置,右下角是约会的地点。‘.’代表马路,‘*’代表房屋。飘飘乎居士只能沿着‘.’行走(也就是不能踏入‘*’),而且行走的方向只能为上下左右的相邻格子。为了不让MM等待太久,飘飘乎居士在整个过程中可能会使用一次飘飘神功(也可能不使用,但最多使用一次),使用飘飘神功后,飘飘乎居士可以走进房屋一次(也就是在全程的行走中最多可以走一个‘*’,注意,只有一个);       现在飘飘乎居士想要知道最少需要走多少步,飘飘乎居士才能到达约会的地点。

输入

第一行,2个正整数  n和m,表示一个n*m的矩阵           接下来n行,每行m个字符,字符一定为  ’.’  或者是‘*’  ,分别代表马路和房屋。           输入数据保证左上角和右下角都为‘.’

输出

一行,如果可以到达,则输入需要行走的最少步数(飘飘神功也记为一步)                         如果不可以到达,则输出‘no’

样例输入输出

输入#1 复制
3 3
.*.
...
...
输出#1 复制
4
输入#2 复制
3 3
.**
***
**.
输出#2 复制
no

提示

0< N  M  < =1000

序号 标题 作者 发表时间 费用 订购数 操作