科学家海豹困在冰山上
Introduction
一家海豹被困在北极圈的冰山上。冰山上有一个无线电发射机，海豹可以用它来呼救。然而，只有爸爸的海豹知道如何操作无线电发射机。更糟糕的是，一年中的这个时候，冰非常滑，所以海豹会失控地滑行，直到它们撞到另一只海豹或者从冰山边缘滑落，这使得爸爸海豹很难到达无线电发射机。幸运的是，其中一只海豹是一位计算机科学家，所以她决定编写一个程序，想出如何将爸爸的封条操纵到无线电发射机上。由于冰上没有足够的空间来编写程序，她决定让程序使用尽可能少的字节。
输入描述
海豹的程序将接受来自STDIN、命令行参数或用户输入函数(如raw_input())的输入。它不能在变量中预先初始化(例如：“此程序期望变量x中的输入”)。
输入的第一行由两个以逗号分隔的整数组成。
A,B下面是由每个B字符组成的A行。每一行只能包含下列字符：
.：寒冷，寒冷，海洋。地图上永远都有这条边界。#：冰山的一部分。a.z：一只不是冰山上的爸爸印章的海豹。D：冰山上的爸爸封印。*：无线电发射机。
(请注意，爸爸印章总是用大写字母D标注的。小写d只是一个普通的印章。)
输出描述
根据下面关于海豹如何移动的规则，输出一份关于封条应该如何移动的指令列表，以便把爸爸的封条送到无线电发射机。
- 规则:所有封条都可以向上(
U)、向下(D)、左(L)和右(R)移动。他们不能斜滑。 - 规则:一只海豹在移动时会继续向同一方向移动，直到它与另一只海豹相撞或掉进海里。
- 如果一只海豹与另一只海豹相撞，它就会停止移动。它与之相撞的封印不会移动。
- 如果海豹掉进海里，它就会淹死，从地图上消失。也就是说，它不是其他封条的对撞机，也不能再移动。
- 规则:两只海豹不能同时移动，在另一只还在移动的时候，印章也不能移动。下一个印章只能在先前的印章停止移动后才能移动。
- 规则:不限制多次移动海豹，也不限制溺水的海豹数量。
- 规则:正确的解决方案将在无线电发射机的爸爸密封端。爸爸的密封不能简单地通过发射机，同时滑动。
输出将由几行组成，每一行的形式如下：
A,B其中A是要移动的印章(D代表爸爸印章，a.z代表其他人)，B是移动印章的方向( U、D、L或R)。请注意，您不需要找到最短的路线。任何让爸爸封印到目标的路线都是可以接受的输出。
示例输入和输出
输入：
25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................输出：
D,R输入：
9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........产出(多项产出中的一项)：
m,R
b,L
D,U
D,R
D,D
D,L输入：
26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................产出(多项产出中的一项)：
v,D
D,L如果您有任何其他问题，请在评论中提出。
回答 1
Code Golf用户
发布于 2015-05-12 06:14:15
Python 3,520字节
R=range
g=[list(input())for i in R(int(input().split(',')[1]))]
f=set(sum(g,[]))-set(".#*")
L=8
def P(p,g):
if len(p)>L:return
for s in f:
c=sum(y.index(s)for y in g if s in y)
if c<1:continue
r,=[n for n in R(len(g))if s in g[n]]
for d in R(4):
m=p+s+",%s\n"%"LURD"[d];G=[y[:]for y in g];o="#";i,j=I,J=r,c
while"#"==o:G[i][j]="#";G[I][J]=s;i,j=I,J;I,J=i+d%2*(d-2),j+(~d%-2&d-1);o=G[I][J]
if"."==o:G[i][j]="#"
if"D"==s:
if"."==o:continue
if"*"==o:print(m);1/0
P(m,G)
while 1:P("",g);L+=4如果人们愿意的话，我稍后可能会做一个更详细的解释，但是基本上，这在可能的移动的状态空间上运行了一个深度优先搜索与迭代深化。如果一个动作导致爸爸的海豹掉下来，它会立即被拒绝。如果爸爸在发送器旁边结束，则打印移动顺序，程序除以零强制退出。
我可以通过在第二行(最后一行为8个额外字节)添加if G!=g:来使代码运行得更快--这将拒绝任何不改变任何内容的移动，例如第一个测试用例中的k,L。
运行时在一次运行到下一次运行时有明显的变化，即使有相同的输入--这显然是因为我通过迭代set来选择下一个印章来移动，这是一个无序的类型。我把第二个测试用例的时间定在5分30秒，尽管我第一次运行它的时间似乎并不长。有了上面提到的优化，它更像是40秒。
https://codegolf.stackexchange.com/questions/50042
复制相似问题
腾讯云开发者
