Calculate minimum distance from the start to the goal

Assignment Help Computer Engineering
Reference no: EM13264789

We are planning an orienteering game. The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.

However, the players have to pass all the checkpoints on the map.

An orienteering map is to be given in the following format. ######## #@....G# ##.##@## #[email protected]# #@.....# ######## In this problem, an orienteering map is to be given.

Calculate the minimum distance from the start to the goal with passing all the checkpoints -Specification * A map consists of 5 characters as following.

You can assume that the map does not contain any invalid characters and the map has exactly one start symbol ''S'' and exactly one goal symbol ''G''. * ''S'' means the orienteering start. * ''G'' means the orienteering goal. * ''@'' means an orienteering checkpoint. * ''.'' 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 (up, down, left, or right) to thenext block.Other types of movements, such as moving diagonally (left up, right up, left down and right down)and skipping one or more blocks, are NOT permitted. * You MUST NOT get out of the map. * Distance is to be defined as the number of movements to the different blocks. * You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary * You can assume that parameters satisfy following conditions. * 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.

Input: The input is to be given in the following format, from the standard input. W H Row1 Row2 ... Row The first row is to describe the width and the height of the orienteering map, sectioned by a space.

From the second row, map information is to be given for exactly the same number of rows as the height.

Each row contains exactly the same number of letters as the width.See "Specification" for details of the symbols contained in the map. Output: Output into the standard output, and put a return.

Reference no: EM13264789

Questions Cloud

Explain the fingerprint region of the ir spectrum : In the fingerprint region of the IR spectrum, what do the absorptions at 746 and 688 cm-1 tell you about the substitution pattern of this compound
How big will be torque on shaft of motor is efficiency : mutual shifted by 90 degree currents through each of both windings of the single phase A motor are (5.5+1.7) A but RMS voltage of the supply is 220 V. How big will be torque on shaft of the motor is efficiency factor (\eta\) is 0.7
Which break-even sales level is usually lower : For the same project, which break-even sales level is usually lower, the net present value breakeven or the income breakeven? Pick one
What is a black swan event : What is a Black Swan event? Does it ever make sense a priori to devote resources to preventing a black swan event?  Explain. Does it ever make sense a priori to devote resources to containing a black swan event should one occur?  Explain.
Calculate minimum distance from the start to the goal : Calculate the minimum distance from the start to the goal with passing all the checkpoints -Specification - The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.
Compute the concentration of iron chloride contaminant : Calculate the concentration of iron (II) chloride contaminant in the original groundwater sample. Round your answer to significant digits.
How much noise should we expect at output of the amplifier : if we have an amplifier whose spec. is 2nV/rtHz and the bandwidth of the amplifier extends from 100Hz to 10kHz, and the gain of the amplifier is 5, how much noise should we expect at the output of the amplifier
Explain how many milligrams of digitalis should a 180 lb : At a dosage of 18 micrograms/kilograms body weight, how many milligrams of digitalis should a 180 lb. patient receivec
Favorite advertising subjects is subliminal advertising : One of my favorite advertising subjects is subliminal advertising. What do you think? Is it going on and we don't know it? Describe how you think subliminal perception could be used by marketers to the detriment of us consumers

Reviews

Write a Review

 

Computer Engineering Questions & Answers

  Define how layers in fireworks work

define how layers in Fireworks work

  Suppose poisson arrivals and departures at each router

A CPU in a router can process 2 million packets/sec. The load offered to it is 1.5 million packets/sec. If the route from source to destination contains 10 routers (having no additional traffic), how much time is spent being queued and serviced by..

  How will you access the size attribute of building

Write down a declaration for all three classes using the principles of inheritence. Make the Building class abstract.

  The least number of telephones an end office

take a simple telephone network consisting of two end offices and one intermediate switch with a 1-MHz full-duplex trunk between each end office and the intermediate switch.

  Program requests the name of food and number of calories

The council suggest that at most 30% of the calories in our diet come from fat. however food labels give the number of calories and amount of fat per serving, they often do not give percentage of calories from fat.

  What circumstances will you use flash over an html editor

Flash is a popular tool to enhance site interactivity. I require recommendations for how to integrate Flash into a website effectively. Under what circumstances would you use Flash over an HTML editor?

  Define the performance of your sql server 2000 installation

What could be done within the database itself to increase performance? Be sure to cite your sources.

  Imagine that a doubly linked list "header"

Assume that a doubly linked list "header" stores the elements of a priority queue. make use of the function pop(), which deletes the element with the largest value from the list (priority queue).

  Writing report with apa format

Select one of the following languages: Modula, Pascal, Ada, C++, C, C#, Java or other instructor-approved language.

  Assume a direct access file consists of sectors

assume a direct access file consists of sectors with 1024 byte capacity. Suppose also that records are 32 bytes long. On which logical sector do the following logical records lie? What is the relative record number in the sector?

  Designing the bits for four octets of ip addres

A firm allocated the network part 128.171. It chooses an 8-bit subnet part. a) Design the bits for four octets of IP address of first host over the first subnet.

  Recognizing the error in code

Suppose that the variable A is an arrays of ints. Take the following code segment:Boolean flag = false;

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd