Jordi, the architect of a construction company, received a request from a customer for an estimate for the construction of a raceway. According to the raceway design drawing provided, the raceway site is in the form of an N x N square grid, each grid being 1 x 1. In the design drawing, the cells in each grid are filled with 0 or 1, where 0 indicates that the cells are empty and 1 indicates that the cells are filled with walls.The starting point of the raceway is the (0, 0) space (top left), and the end point is the (N-1, N-1) space (bottom right).
Jordi must build a raceway so that the car from the starting point (0, 0) can safely reach the destination (N-1, N-1). A raceway can be constructed by connecting two adjacent blank spaces up, down, left and right, and a raceway cannot be built in a wall with walls. At this time, a raceway that connects two adjacent blank spaces up and down or left and right is called a straight road.
Also, the point where two straight roads meet each other at right angles is called a corner. Calculating the construction cost, it costs 100 $ to make a straight road, and 500$ to make a corner.
Jordi needs to calculate the minimum cost required to build a raceway in order to make an estimate.
If you build a raceway like the red one, it costs 3200 won for 12 straight roads and 4 corners. If you build a raceway like the blue path, it costs a total of 3,500 won for 10 straight roads and 5 corners, and it costs more.
My code consumes lots of running time... my new idea is making an library. key value of(x,y). If BFS arrives at (x,y) first time it saves the cost to reach (x,y). If BFS arrives (x,y) again, and it's cost is compared with value existing. and if it bigger than value, it is not added to BFS how's this idea? i did not use this idea on code because i'm afraid this would take long time too.
and i wonder your idea too there is a hint but i could not understand it
My code(original code, new idea not used)
from collections import deque import copy def check(a,b,board,n): #checks if it can be added to queue# if b=='U': if a>0 and board[a-1][a]!=1 and [a-1,a] not in a: return True if b=='D': if a<n-1 and board[a+1][a]!=1 and [a+1,a] not in a: return True if b=='R': if a<n-1 and board[a][a+1]!=1 and [a,a+1] not in a: return True if b=='L': if 0<a and board[a][a-1]!=1 and [a,a-1] not in a: return True return False def move(a,b): # append next movement to queue, change direction and add Turn counts if b==a: if b=='U': a-=1 return a if b=='D': a+=1 return a if b=='R': a+=1 return a if b=='L': a-=1 return a else: if b=='U': a+=1 a-=1 a='U' return a if b=='D': a+=1 a+=1 a='D' return a if b=='R': a+=1 a+=1 a='R' return a if b=='L': a+=1 a-=1 a='L' return a def solution(board): value= n=len(board) d=0 queue=deque() # In queue i added elements [current location, Direction,Turn Counts,visited dots in list] queue.append([[0,0],'R',0,]) queue.append([[0,0],'D',0,]) while len(queue)!=0: p=queue.popleft() #to use differnt lists in case of error in if loop Up=copy.deepcopy(p) Down=copy.deepcopy(p) Right=copy.deepcopy(p) Left=copy.deepcopy(p) past=p Up.append(past) Down.append(past) Left.append(past) Right.append(past) p.append(past) #I thought the cheapest route can not be longer than shortest route+3 if d!=0 and len(p)>d+3: answer = min(value)*100 return answer if p==[n-1,n-1]: value.append((len(p)-1)+5*p) d=len(p)-1 if check(Up,'U',board,n)==True: queue.append(move(Up,'U')) if check(Down,'D',board,n)==True: queue.append(move(Down,'D')) if check(Right,'R',board,n)==True: queue.append(move(Right,'R')) if check(Left,'L',board,n)==True: queue.append(move(Left,'L')) answer = min(value)*100 return answer
hint(just for reference)
For the lowest cost with K corners, you can reduce the number of straight roads as much as possible. This is done by making K corners and finding the shortest route from the origin to the destination.
Now we define the state space S as follows:
- [Vertical coordinate R][Horizontal coordinate C][Number of corners K][Looking direction D] → Shortest distance when arriving at the (R, C) position while making K corners and looking at direction D
At this time, it is assumed that the cost of moving one space is 1, and the cost of creating a corner is also 1. Now it finds the shortest route to the origin → destination for all Ks. The BFS search code is written as follows:
- Based on the last viewed direction, it searches for three cases: turning left, turning right, and going straight.
- In the case of left and right rotation, add a corner and change the viewing direction.
- In the case of going straight, advance one space in the direction you are looking.
After searching for BFS as above, finally K = 1, 2, 3,… at (N – 1, N – 1) position. Find the shortest distance for the case. At this time, it is important to note that the shortest distance obtained here is a value including the number of corners. Therefore, in the shortest distance with K corners, the construction cost can be calculated as follows:
- (Shortest distance-K) x 100 + K * 500
So how big can the K value here? Each grid can have a maximum of 1 corner. If so, the number of corners in an N x N grid should be less than the number of grid cells. Therefore, the number of corners K can be at most N x N.