Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- import time
- import numpy as np
- import matplotlib.pyplot as plt
- import os
- sys.setrecursionlimit(99999)
- inpt1 = sys.argv[1]
- blank = "0"
- wall = "250"
- mazel = []
- with open(inpt1,"r") as file:
- row = 0
- for line in file:
- templ = []
- col = 0
- for char in line:
- if char != "\n":
- if char == "F" or char == "S":
- templ.append(char + (len(blank)-1)*blank[0])
- elif char == "P":
- templ.append(blank)
- elif char == "W":
- templ.append(wall)
- if char == "F":
- fx,fy = col,row
- if char == "S":
- sx,sy = col,row
- col += 1
- ma_col = col
- row += 1
- mazel.append(templ)
- ma_row = row
- pic = np.full((ma_col-1,ma_row),0)
- print(f"Start cell {sx},{sy} --- Finish cell {fx},{fy}\n\nHeight: {ma_row}\nWidth: {ma_col}")
- def around(x,y,p):
- u,d,l,r = False,False,False,False
- if y != 0:
- if mazel[y-1][x] == blank or mazel[y-1][x] == "F"+(len(blank)-1)*blank[0] or mazel[y-1][x] == 450:
- if (x,y-1) not in p:
- u = True
- if y != (len(mazel)-1):
- if mazel[y+1][x] == blank or mazel[y+1][x] == "F"+(len(blank)-1)*blank[0] or mazel[y+1][x] == 450:
- if (x,y+1) not in p:
- d = True
- if x != (len(mazel[0])-1):
- if mazel[y][x+1] == blank or mazel[y][x+1] == "F"+(len(blank)-1)*blank[0] or mazel[y][x+1] == 450:
- if (x+1,y) not in p:
- r = True
- if x != 0:
- if mazel[y][x-1] == blank or mazel[y][x-1] == "F"+(len(blank)-1)*blank[0] or mazel[y][x-1] == 450:
- if (x-1,y) not in p:
- l = True
- return (u,d,l,r)
- mazel[sy][sx] = 450
- mazel[fy][fx] = 450
- intersect = []
- vis = []
- path = []
- success_path = []
- stime = time.time()
- def li_copier(f):
- temp = []
- t = []
- for i in f:
- t.append(i[:])
- return t
- takenpath = 0
- def print_m(using,sym):
- global takenpath
- tempm = li_copier(mazel)
- for i,j in using:
- if tempm[j][i] == blank:
- tempm[j][i] = sym
- a = np.array(tempm, dtype=int)
- plt.pcolor(a,cmap="inferno")
- plt.axis("off")
- plt.title(f"Looked through {takenpath} cells in total\nCurrent lenght of the path is {len(using)-1}")
- plt.savefig(f"{takenpath}.png")
- plt.clf()
- takenpath += 1
- def solver(start,finish,taken):
- global takenpath
- for i in intersect:
- if i not in taken:
- l,y = i
- mazel[y][l] = 0
- x,y = start
- branch = taken[:]
- branch.append(start)
- if start != (fx,fy):
- vis.append(start)
- print_m(branch,365)
- #print("----",branch)
- if start == finish:
- #print("Solution found!")
- #print(branch)
- success_path.append(branch[:])
- print("Total cells looked through",takenpath,"cells")
- else:
- #print(x,y)
- u,d,l,r = around(x,y,vis)
- if sum([u,d,l,r]) > 1:
- mazel[y][x] = 450
- intersect.append((x,y))
- if d:
- solver((x,y+1),finish,branch)
- if r:
- solver((x+1,y),finish,branch)
- if l:
- solver((x-1,y),finish,branch)
- if u:
- solver((x,y-1),finish,branch)
- try:
- os.mkdir(f"{inpt1[:-4]}out")
- except:
- pass
- os.chdir(f"{inpt1[:-4]}out")
- solver((sx,sy),(fx,fy),path)
- min_path = success_path[0]
- for i in success_path:
- if len(i) < len(min_path):
- min_path = i
- print(takenpath)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement