You are not logged in. Please login at www.codechef.com to post your questions!

×

How to solve such questions based on maze

 0 An orienteering map is to be given in the following format. ######## #@....G# ##.##@## #..@..S# #@.....# ######## Calculate the minimum distance from the start(S) to the goal(G) with passing all the checkpoints(@). Specification ‘.’ means an opened-block that players can pass. ‘#’ means a closed-block that players cannot pass. It is allowed to move only by one step vertically or horizontally. 1 <= w <= 100, 1 <= h <= 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. The input is to be given in the following format, from the standard input.  W H Row1 Row2 ... RowH  The first row is to describe the width and the height of the orienteering map, sectioned by a space. Output Output into the standard output, and put a return. And later I also have to print the path. asked 13 Aug '16, 15:58 1★arpit728 683●15●62 accept rate: 10%

 0 could you plzz provide the link for this question so that i can understand complete question answered 13 Aug '16, 16:50 16 accept rate: 33% (13 Aug '16, 17:17) arpit7281★ @shobhit99924 Can you help me to code this, I couldn't. It would be great help if you could. (15 Aug '16, 18:59) arpit7281★
 0 You can solve this problem in 2 steps : Step 1: Create a new weighted complete graph from the input matrix , where your can add edges from source to each checkpoint and for any checkpoint to all other checkpoint and from destination to all other checkpoint. In your input example , There are three checkpoints( Let say c1 , c2 , c3 ) , one source(s) , one destination (d) . Then total edges are ( s , c1 ) ( s , c2 ) ( s , c3 ) , (c1 , c2 ) , ( c1 , c3 ) , (c2 , c3 ) ( c1 , d ) ( c2 , d ) ( c3 , d ). And if you can't reach to any checkpoint + destination from source , then you can't create the graph in that case your answer is -1. And the weight of any edge is the shortest distance between them which you can calculate by apply flood fill or any other algo like dfs/bfs on the input matrix. Step 2: Now you have complete graph , from that you have to calculate the shortest minimum path from source to destination where in between the path you have to traverse all checkpoint exactly once , means you have to find the open path from source to destination where you have to traverse all nodes exactly once. This can be solve using recursion + optimazation ( backtracking type ). In your example total possible path are : s - c1 - c2 - c3 - d s - c1 - c3 - c2 - d s - c2 - c1 - c3 - d s - c2 - c3 - c1 - d s - c3 - c1 - c2 - d s - c3 - c2 - c1 - d The one which will give you the minimum cost is your answer. answered 13 Aug '16, 17:25 322●8 accept rate: 23% @vipsharmavip Can you help me to code this, I couldn't. It would be great help if you could. (15 Aug '16, 18:58) arpit7281★
 0 First start a BFS from each of the checkpoints, and start and finish, in order to determine the minimum distances between any pair of checkpoints (or the start and finish). Then you've reduced the problem to the Travelling salesman problem, for which you can code a DP solution using bitmasks and solve in O(2^n * n), which is fast enough for only 18 checkpoints. I can describe the solution in more detail if you'd like. Here's a similiar problem on SPOJ: http://www.spoj.com/problems/CLEANRBT/ answered 13 Aug '16, 17:18 4★linkret 236●5 accept rate: 25% @linkret I understand the logic, please tell me more details about implementation part. (14 Aug '16, 07:56) arpit7281★ @linkret Later I also need to find the actual path. (14 Aug '16, 07:57) arpit7281★ @linkret Can you help me to code this, I couldn't. It would be great help if you could. (15 Aug '16, 18:59) arpit7281★
 toggle preview community wiki:
Preview

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,197
×125
×30

question asked: 13 Aug '16, 15:58

question was seen: 1,949 times

last updated: 15 Aug '16, 18:59