群岛地图(和一条河流)
群岛地图(和一条河流)
提问于 2015-05-30 03:46:33
Introduction
几个世纪以来，有一条河流从未被绘制过地图。制图家协会想要制作一张河流地图，但是他们从未成功--出于某种原因，他们派去绘制河流地图的所有制图师都被该地区的野生动物吃掉了。需要采取不同的办法。
输入描述
该区域是由长度m和宽度n的单元格组成的矩形网格。左下角的单元格是0,0，右上角的单元格是m-1,n-1。m和n作为元组m,n在输入中提供。
利用远距离地理探测技术，确定了河流周围岛屿的位置。岛屿的大小(即岛所占的细胞数)也已确定，但形状尚未确定。我们在元组s,x,y中提供这个信息，其中s是岛的大小，x和y是那个岛的一个特定单元格的x和y位置。输入中的每个元组都是分隔的，下面是一个示例输入：
7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6为了更清楚地说明，下面是图的输入：
y 6|8 1 3
5|
4| 2
3| 2
2|
1| 2 2
0|2
=======
0123456
x输出描述
输出一个使用ASCII字符表示区域部分的地图。每个细胞要么是# (陆地)，要么是. (水)。地图应遵循以下规则：
- 定义。岛屿是一组正交的陆地细胞群，完全被河流细胞和/或该区域的边界所包围。
- 定义。河流是一组正交的水细胞群，完全被陆地细胞和/或区域边界所包围，不包含“湖泊”(2x2区的水细胞)。
- 规则。地图上应有一条河。
- 规则。输入中的每个编号单元应是包含精确
s单元的岛的一部分。 - 规则。地图中的每个岛屿都必须包含输入中的一个编号单元格。
- 规则。每个输入都有一个唯一的映射。
下面是示例输入的输出：
#.#.##.
#....#.
#.##...
##..##.
###....
...##.#
##....#这是另一个输入和输出。
输入：
5,5 3,0,1 1,4,1 2,0,4 2,2,4 2,4,4输出：
#.#.#
#.#.#
.....
###.#
.....回答 1
Code Golf用户
发布于 2018-08-21 21:48:09
Python 3，1295字节
这是python唯一的解决方案。它不使用库，并通过标准输入加载板。接下来的进一步解释。这是我第一次尝试这么大的高尔夫球。在底部有一个链接到注释和无金色代码。
L,S,O,R,F=len,set,None,range,frozenset
U,N,J,D,I=S.update,F.union,F.isdisjoint,F.difference,F.intersection
def r(n,a,c):
U(c,P)
if L(I(N(Q[n],C[n]),a))<2:return 1
w=D(P,N(a,[n]));e=S();u=S([next(iter(w))])
while u:n=I(Q[u.pop()],w);U(u,D(n,e));U(e,n)
return L(e)==L(w)
def T(a,o,i,c,k):
s,p,m=a
for _ in o:
t=s,p,N(m,[_]);e=D(o,[_])
if t[2] in c:o=e;continue
c.add(t[2]);n=D(Q[_],m);U(k,n)
if not J(i,n)or not r(_,N(m,i),k):o=e
elif s==L(t[2]):yield t
else:yield from T(t,N(e,n),i,c,k)
s,*p=input().split()
X,Y=eval(s)
A=[]
l=1,-1,0,0
P=F((x,y)for y in R(Y)for x in R(X))
exec("Q%sl,l[::-1]%s;C%s(1,1,-1,-1),l[:2]*2%s"%(('={(x,y):F((x+i,y+j)for i,j in zip(',')if X>x+i>-1<y+j<Y)for x,y in P}')*2))
for a in p:a,x,y=eval(a);k=x,y;A+=[(a,k,F([k]))]
A.sort(reverse=1)
k=F(a[1]for a in A)
p=[O]*L([a for a in A if a[0]!=1])
g,h=p[:],p[:]
i=0
while 1:
if g[i]is O:h[i]=S();f=O;g[i]=T(A[i],Q[A[i][1]],D(N(k,*p[:i]),[A[i][1]]),S(),h[i])
try:p[i]=g[i].send(f)[2]
except:
f=I(N(k,*p[:i]),h[i]);g[i]=p[i]=O;i-=1
while J(p[i],f):g[i]=p[i]=O;i-=1
else:
i+=1
if i==L(p):
z=N(k,*p)
if not any(J(z,F(zip([x,x+1]*2,[y,y,y+1,y+1])))for x in R(X-1)for y in R(Y-1)):break
for c in h:U(c,z)
b=[X*['.']for i in R(Y)]
for x,y in z:b[y][x]='#'
for l in b[::-1]:print(''.join(l))页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/51006
复制相关文章
相似问题
腾讯云开发者
