每日一题 | 迷宫

    接下来我们一起来看一下题目的描述吧！！！

迷宫（labyrinth）

【问题描述】

    鹏鹏在一个迷宫里困住了。

    迷宫是长方形的，有n行m列个格子。一共有3类格子，空地用字符’.’表示，墙壁用’#’表示，陷阱用’*’表示。特别地，迷宫中有两个特殊的格子：起点用’S’表示；终点用’E’表示。起点和终点都是空地。（’S’和’E’均为大写字母）

    鹏鹏的任务是：从起点出发，沿着某条路径，走到终点。

游戏对路径的要求有三条：每次只能向相邻格子（上/下/左/右）移动一步；不能经过墙壁（即可以经过空地和陷阱）；不能走出迷宫边界。

    聪明的你请告诉鹏鹏，他能完成任务吗？如果能，鹏鹏能否不经过任何陷阱就完成任务呢？

    第一行为两个整数n，m（2≤n，m≤7）。

    接下来有n行，每行是一个长度为m的字符串，依次表示迷宫的每一行格子。

    仅有一行，是一个字符串。

    如果鹏鹏可以不经过任何陷阱就到达终点，输出”goOD”；否则，如果经过若干陷阱能到达终点，输出”0K”；否则，输出”BAD”。（所有字母均为大写）

3 4

##.E

S*.#

…*

3 3

##E

S*.

#..

##67

1*5#

234*

样例1的最优路线为1->2->3->4->5->6->7，如上图。