Руби, 414 символов
$ cat problem
4.4.1
.....
4.6.2
.....
..1..
$ python bridges.py problem
4=4-1
$ |
4=6=2
|
1
Пример:
import sys
from itertools import product,combinations
e=[]
p=[[[0,(c,r,o,[])][c!='.'] for o,c in enumerate(l.strip())] for r,l in enumerate(open(sys.argv[1]))]
r=range(len(p))
c=range(len(p[0]))
for i,j in combinations(product(r,c),2):
if p[i[0]][i[1]] and p[j[0]][j[1]]:
if i[0]==j[0] and abs(i[1]-j[1])>1:
b=1
g=range(min(i[1],j[1])+1,max(i[1],j[1]))
for x in g:
if p[i[0]][x]:b=0
if b:e+=[(i,j,[i[0]],g,1)]
if i[1]==j[1] and abs(i[0]-j[0])>1:
b=1
g=range(min(i[0],j[0])+1,max(i[0],j[0]))
for x in g:
if p[x][i[1]]:b=0
if b:e+=[(i,j,g,[i[1]],0)]
def s(v,i,m):
if i>=len(v):
return None
for j in [2,1,0]:
v[i]=j
q=dict(m)
b=1
for l in [0,1]:
n=e[i][l]
if not n in q:q[n]=0
q[n]+=j
y=int(p[n[0]][n[1]][0])
if q[n]>y:b=0
if not b:continue
a=[d for b in range(i+1) for d in product(e[b][2],e[b][3]) if v[b]>0]
if len(a)!=len(set(a)):continue
if i==len(v)-1:
g=1
for l,z in product(r,c):
n=p[l][z]
if not n:continue
if q[(n[1],n[2])]!=int(n[0]):g=0
if g:return v
u=s(v,i+1,q)
if u:return u
for i,v in zip(e,s([None]*len(e),0,{})):
if v>0:
for j,k in product(i[2],i[3]):p[j][k]=[[['|','$'][v-1],['-','='][v-1]][i[4]]]
for l in p:
for c in l:
if not c:c=[' ']
sys.stdout.write(c[0])
print ""
||answer||
Питон 3/ 1780C
Эту задачу можно преобразовать в задачу точного покрытия. Мы можем использовать Кнута АлгоритмX чтобы решить точную проблему покрытия.
Подробности о преобразовании входных данных в матрицу 0-1 я опубликую позже. Это очень интересно.
Решение проблемы точного покрытия с помощью AlgorithmX происходит очень быстро. На моей машине пример был решен за 0,09 секунды, за 310 итераций. И программа может выводить все решения.
import sys
from itertools import product as I
a=sys.stdin.read().split()
V=list
L=len
Z=enumerate
W=range
P=V(I(W(L(a)),W(L(a[0]))))
E={p:[]for p in P}
Q={(i,j):int(a[i][j])for i,j in P if'.'!=a[i][j]}
J=Q.items()
F=[]
for p,c in J:
for i,j in((0,1),(1,0)):
q=p[0]+i,p[1]+j;e=[p,0]
while q in P:
E[q]+=[e]
if q in Q:e[1]=q;E[p]+=[e];F+=[e];break
q=q[0]+i,q[1]+j
E={x:[x for x in y if x[1]!=0]for x,y in E.items()}
C=[E[p] for p in P if p not in Q and L(E[p])>1]
m=[]
T=L(Q)+4*L(F)+L(C)
s=0
l={}
for p,c in J:
e=E[p];u=L(e)*2
for t in I(*((0,1,2)for x in e)):
if sum(t)!=c:continue
r=[0]*T;r[s+u]=1
for i,x in Z(t):k=s+i*2;r[k:k+2]=((1,1),(0,1),(0,0))[x]
m+=[r]
l[p]=s;s+=u+1
z=L(m)
for e in F:
p,q=e;r=[0]*T;c,d=l[p]+E[p].index(e)*2,l[q]+E[q].index(e)*2;t=r[:];r[c]=r[d]=1
for i,u in Z(C):r[T-L(C)+i]=int(e in u)
t[c+1]=t[d+1]=1;m+=[r,t]
def I(x,d):
y=d[x]
while y!=x:yield y;y=d[y]
def A(c):
L[R[c]],R[L[c]]=L[c],R[c]
for x in I(c,D):
for y in I(x,R):U[D[y]],D[U[y]]=U[y],D[y]
def B(c):
for x in I(c,U):
for y in I(x,L):U[D[y]],D[U[y]]=y,y
L[R[c]],R[L[c]]=c,c
def S():
c=R[h]
if c==h:yield[]
A(c)
for r in I(c,D):
for x in I(r,R):A(C[x])
for t in S():yield[r[0]]+t
for x in I(r,L):B(C[x])
B(c)
L,R,U,D,C={},{},{},{},{}
h=T
L[h]=R[h]=D[h]=U[h]=h
for c in W(T):
R[L[h]],R[c],L[h],L[c]=c,h,c,L[h];U[c]=D[c]=c
for i,l in Z(m):
s=0
for c in I(h,R):
if l[c]:
r=i,c;D[U[c]],D[r],U[c],U[r],C[r]=r,c,r,U[c],c
if s==0:L[r]=R[r]=s=r
R[L[s]],R[r],L[s],L[r]=r,s,r,L[s]
for s in S():
b=V(map(V,a))
for e in s:
if e<z:continue
(i,j),(x,y)=F[(e-z)//2]
if j==y:
for r in W(i+1,x):b[r][j]='|H'[b[r][j]=='|']
else:
for r in W(j+1,y):b[i][r]='-='[b[i][r]=='-']
print('\n'.join(''.join(l)for l in b).replace('.',' '))
||answer||
Питон: 1303 символа
Это какой-то очень уродливый код, и он не особенно эффективен, но я считаю, что он работает:
2.2.5.2.
.....1.3
6.3.....
.2..6.1.
3.1..2.6
.2......
1.3.5..3
.2.3..2.
2 2-5=2
$ | $1-3
6=3 $ $
$2--6-1$
3|1 $2=6
|2| $ $
1|3=5--3
2-3==2
Пример:
h=->l,s,v{l[s.index(v)||s.size]}
c=->r,f{r[f].to_i-h[[1,2,0],'|$',r[f-N]]-h[[1,2,0],'-=',r[f-1]]-h[[1,2,0],'-=',r[f+1]]}
s=->r{(f=r=~/\./)&&(m=h[[2,4,25,25,25,31],w='|$-= ',a=r[f-N]]&h[[7,7,8,16,7,31],w,r[f-1]]
a=~/\d/&&m&=(0>d=c[r,f-N])?0:d<1?25:d<2?2:d<3?4:0
' |$-='.chars{|k|m&1>0&&(r[f]=k;s[r]);m=m>>1};r[f]='.')||r[-N..-1]=~/^ +$/&&$><<r[N..-N].tr("0",$/)}
N=1+((t=STDIN.read)=~/$/)
s[$/*N+t.tr($/,"0")+"."*N]
![[Э.А. Коэттинг] Призывая вечность. Запретные обряды эвокации](/assets/images/icons/forum0.png){kind=icon}
![[Udemy] Легкое создание продающих адаптивных веб-страниц (2019)](/assets/images/icons/forum7.png){kind=icon}
![[А. Парабеллум, Н. Мрочковский] Продажа тренингов и семинаров](/assets/images/icons/forum6.png){kind=icon}
![[виктор Рогов] Первые 100.000 Рублей Из Instagram](/assets/images/icons/forum5.png){kind=icon}