lintcode|lintcode 1751 牛郎织女
【lintcode|lintcode 1751 牛郎织女】又到了七夕节，牛郎织女相约一起去一个nm大小的迷宫maze里玩耍。然而没过多久，他们就倒霉地走散了。现在给定由.,,S,T组成的矩阵maze，其中.表示空地,*表示障碍物,S表示牛郎的位置 ,T表示织女的位置，牛郎和织女都会试图寻找对方，不停地在矩阵中走动(他们可以每次向上下左右四个方向移动一格或者站着不动，但是不能走到迷宫外面或者障碍物)，请问他们是否有可能重逢?如果有可能，返回True，否则返回False。
样例1:输入:
[
"S..*",
"*.**",
"...T"
]
输出: true
说明:
织女选择不动
牛郎行动路线(0,0)->(0,1)->(1,1)->(2,1)->(2,2)->(2,3)
样例2:输入:
[
"S..*",
"***.",
"...T"
]
输出: false
说明：
这两个人无论如何和碰不上了
注意事项
2<=n,m<=1000
推荐阅读
- 旋转字符串
- lintcode-线段树查询I
- Lintcode119|Lintcode119 Edit Distance solution 题解
- lintcode|lintcode A+B问题
- POJ - 1751Highways （最小生成树）
- Lintcode363 Trapping Rain Water solution 题解
- Lintcode364 Trapping Rain Water II solution 题解
- Lintcode364.Trapping Rain Water II