迷宫
* * * *
拉格朗日计划
* * * *
迷宫

给定一个迷宫,找出从入口(用S表示)到出口(用E表示)的最短路径,用“.”标记该路径后输出,如下例:

###########        ###########
#S#      E#        #S#  ....E#
# ### #####        #.###.#####
#   #     #   ->   #...#.....#
### ##### #        ###.#####.#
#         #        #  .......#
###########        ###########


本题难度:



解答

本题所给的迷宫似乎都只有一条路径,作深度优先搜索(否则应该作广度优先搜索,但代码略长)即得结果。

最终代码有九行。

代码长度:194字节 vs. 全站第一:116字节。

import sys
a=sys.argv[1]
n,s=a.find("\n")+1,[[a,a.find("S")]]
while s:
  g,p=s.pop()
  for k in[p+1,p-1,p+n,p-n]:
   if 0<=k<len(g)and g[k]in" E":g[k]=="E"==print(g);s.append([g[:k]+"."+g[k+1:],k])