14,634,917 members
Rate this:
See more:
Can anyone please convert my python code into c++
Description of the Problem: A postman is delivering mails in a square-shaped town. He starts from the start (S) and would arrive at the goal (G). On the way, he has to deliver mails at some checkpoints (X). Calculate the minimum distance the postman has to travel from the start to the goal while passing all the checkpoints.

Remarks: 'S' = start point 'G' = goal point 'X' = checkpoint '.' = open-block that the postman can pass '#' = closed-block that the postman cannot pass

A movement means a vertical or horizontal step (up, down, left or right)
Other types of movements, such as moving diagonally, or skipping one or more blocks, are NOT allowed.
The postman cannot get out of the map.
Distance is defined as the number of movements
The postman CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.
You can assume 1<=width<=100, 1<=height<=100.
The maximum number of checkpoints is 18.
Return -1 if given arguments do not satisfy specifications, or players cannot arrive at the goal from the start by passing all the checkpoints.

Idea: BFS. Steps are as follow:

find locations of S, all checkpoints X (in a list), and goal G
use BFS to get shortest paths from S to each checkpoint X. Save in List. Each checkpoint is matched under the same list index Return -1 if not reachable
get shortest paths from each X to each other X
get shortest path from each X to the G
find shortest distance from starting point, via all midway checkpoints to the ending point

Assumptions: only has one goal point and one starting point.

What I have tried:

Question: Delivery problem with mid-way checkpoints
Town Setting: In a 2-D Matrix
'G': goal
'X': checkpoint
'S': starting point
0 : open block
1 : closed block
Idea: BFS. Steps are as follow:
1. find locations of S, all checkpoints X (in a list), and goal G
2. use BFS to get shortest paths from S to each checkpoint X. Save in List.
Each checkpoint is matched under the same list index
Return -1 if not reachable
3. get shortest paths from each X to each other X
4. get shortest path from each X to the G
5. find total shortest distance from starting point, via all midway checkpoints to the ending point
Assumptions: has and only has one goal point and one starting point.
"""
from collections import deque
from Node import Node
import itertools
import sys

class Solution(object):
def delivery(self, matrix):
# Step 1: get the location of start_point, goal_point, all checkpoints
start_point = ()
check_points = []	# List of point tuples
goal_point = ()
row_nums = len(matrix)
col_nums = len(matrix[0])
for i in range(row_nums):
for j in range(col_nums):
if matrix[i][j] == 'S':
start_point = (i,j)
elif matrix[i][j] == 'G':
goal_point = (i,j)
elif matrix[i][j] == 'X':
check_points.append((i,j))

if len(check_points) == 0:
print "No Checkpoint Exists"
return -1

# Step 2. Find shortest paths from 'S' -> Each 'X'
S_X_paths = []
for i in range(len(check_points)):
check_point = check_points[i]
# BFS
queue = deque([])
queue.append(Node([],start_point))
visited = set()

while queue:
node = queue.popleft()
location = node.cur		# Tuple
prev = node.prev		# List

# Checkpoint reached. Record this path.
if location == check_point:
prev.append(location)
S_X_paths.append(prev)
break

for action in self.actions(matrix, location):
if action in visited:
continue
newPath = prev + [location]
queue.append(Node(newPath, action))
# Some checkpoints are not reachable. Return -1
if len(check_points) != len(S_X_paths):
print "Some Checkpoints Are Unreachable"
return -1

# Step 3. Find shortest paths between each 'X' <-> each other 'X'
X_X_paths = []
for i in range(len(check_points)):
start = check_points[i]
for j in range(i+1, len(check_points)):
end = check_points[j]
# BFS
queue = deque([])
queue.append(Node([],start))
visited = set()
while queue:
node = queue.popleft()
location = node.cur		# Tuple
prev = node.prev		# List

# Checkpoint reached. Record this path.
if location == end:
prev.append(location)
X_X_paths.append(prev)
break

for action in self.actions(matrix, location):
if action in visited:
continue
newPath = prev + [location]
queue.append(Node(newPath, action))

# Step 4. Find shortest paths from each 'X' to 'G'
X_G_paths = []
for check_point in check_points:
# BFS
queue = deque([])
queue.append(Node([],check_point))
visited = set()

while queue:
node = queue.popleft()
location = node.cur		# Tuple
prev = node.prev		# List

# Goal reached. Record this path.
if location == goal_point:
prev.append(location)
X_G_paths.append(prev)
break

for action in self.actions(matrix, location):
if action in visited:
continue
newPath = prev + [location]
queue.append(Node(newPath, action))
# Some checkpoints cannot reach goal. Return -1
if len(check_points) != len(X_G_paths):
print "Some Checkpoints Cannot Reach The Goal"
return -1

# Step 5. Find minimum path from S to G via all X
# 3 sets of dictionaries to store path costs
S_X_dic = {}
for path in S_X_paths:
S_X_dic[path[-1]] = len(path) - 1
X_dic = {}
for path in X_X_paths:
X_dic[(path[0], path[-1])] = len(path) - 1
X_G_dic = {}
for path in X_G_paths:
X_G_dic[path[0]] = len(path) - 1

# Generator to get different paths
gen = itertools.permutations(check_points)
res_path = []
min_length = sys.maxint
while True:
try:
path = [start_point] +  list(gen.next()) + [goal_point]
length = 0
for i in range(len(path)-1):
# S -> X
if i == 0:
x = path[i+1]
length += S_X_dic[x]
elif i == len(path)-2:
x = path[i]
length += X_G_dic[x]
else:
if (path[i], path[i+1]) in X_dic:
length += X_dic[(path[i], path[i+1])]
else:
length += X_dic[(path[i+1], path[i])]
if length < min_length:
min_length = length
res_path = path
# End iteration
except StopIteration:
break

# Display the path taken
print "Shortest Path:"
print res_path

return min_length

# actions() helper method. Return possible actions from given location
def actions(self, matrix, location):
# rtype: List[Tuple]
res = []
row = location[0]
col = location[1]
if row != 0 and matrix[row-1][col] != 1: res.append((row-1, col))
if row != len(matrix)-1 and matrix[row+1][col] != 1: res.append((row+1, col))
if col != 0 and matrix[row][col-1] != 1: res.append((row, col-1))
if col != len(matrix[0])-1 and matrix[row][col+1] != 1: res.append((row, col+1))
return res
Posted
Updated 11-Mar-20 6:45am
v2
Rick York 10-Mar-20 20:43pm

C++ has a number of collection classes including deque and vector which can be used to construct a matrix (a vector of vectors). You should be able to convert your code fairly easily. The len function appears to be the same as size in the vector class. For a useful reference have a look at https://www.cplusplus.com/

Rate this:

## Solution 1

Longer answer: while we are happy to help with specific technical questions, we are not here to do your work for you. And that includes providing free conversion services.
Rate this:

## Solution 2

Could yes. Will No.

Hints:
Python:
for length < min_length: ...

C++:
for (length < min_length) { ... }

Python:
while queue: ...

C++:
while ( !queue.empty() ) { ... }

Thanks for reminding me why I hate modifying Python code. I would never write anything in it without a gun to my head. Whoever designed it needs to have their head examined, because using white space as part of the syntax is nuts.