1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
|
import sys
sys.setrecursionlimit(500)
import copy
CF=[]
position=[]
SOL=[]
Tab=[]
print("Nombre de vehicules, rouge compris:")
N=int(input())
print("Nombre de vehicules verticaux:")
n=int(input())
print("position et longueur(x,y,l) des vehicules horizontaux, rouge en premier")
for i in range(N-n):
print(i+1)
x=int(input("x: "))
y=int(input("y: "))
l=int(input("l: "))
CF.append((True,y,l))
position.append(x)
print("position et longueur(x,y,l) des vehicules verticaux")
for i in range(n):
print(i+N-n+1)
x=int(input("x: "))
y=int(input("y: "))
l=int(input("l: "))
CF.append((False,x,l))
position.append(y)
print("nombre de coups:")
maxirec=int(input())
lm=1
C=[]
for i in range(len(CF)):
lm=lm*(7-CF[i][2])
C.append(6-CF[i][2])
Tab=[0]*lm
Tab[f2(pos)]=1
rec(position,N,[],1)
H=p(SOL)
H=[position]+H
print(len(H),"mouvements")
for i in range(len(H)-1):
for j in range(N):
a= H[i][j]
b= H[i+1][j]
if a!=b:
sens = "y"
c,d=CF[j][1],a
if CF[j][0]:
sens = "x"
c,d=d,c
print("vehicule n.",j+1,(c,d),":",sens,"=",a,"->",b)
print("vehicule n.",1,(H[len(H)-1][0],2),":","x","=",H[len(H)-1][0],"->","sortie")
def fonction ( n, position):
vehicule = CF[n]
x=vehicule[1]
y= position[n]
l=vehicule[2]
sens = vehicule[0]
bornes=[0,6-l]
for i in range(len(position)):
W=CF[i]
z=position[i]
if i!=n and sens==W[0] and x==W[1]:
if z<y:
bornes[0]=max(bornes[0],W[2]+z)
if z>y:
bornes[1]=min(bornes[1],z-l)
if sens!=W[0] and z<=x and x<=z+W[2]-1:
if W[1]<y:
bornes[0]=max(bornes[0],W[1]+1)
if W[1]>y:
bornes[1]=min(bornes[1],W[1]-l)
return [i for i in range(bornes[0],bornes[1]+1) if i!=y]
def f2(pos):
S=0
p=1
for i in range(len(pos)):
S+=pos[i]*p
p=p*(C[i]+1)
return S
def rec(pos,lng,mvts,k):
H=fonction(0,pos)
if 4 in H :
SOL.append(mvts)
else:
for n in range(lng):
K=fonction(n,pos)
for i in K:
J=copy.copy(pos)
J[n]=i
d=f2(J)
ncoup=Tab[d]
if (ncoup==0 or k<ncoup) and k<maxirec :
Tab[d]=k
M=copy.copy(mvts)
M.append(J)
rec(J,lng,M,k+1)
def p(L):
G=L[0]
m=len(G)
for h in L:
if len(h)<m:
m=len(h)
G=h
return G |
Partager