# C++ problem w/ data structures

A coal mine has collapsed, but we have a seismic picture of a vertical cross-section that shows where all the pockets that might contain workers [url removed, login to view] can drill shafts vertically from the ground to a pocket, or from an already-reached pocket to another pocket. Your program will calculate how many hours it will take to reach all the pockets.

X indicates rock, while - indicates air space. Access within a pocket is limited to horizontal or vertical adjacency. Each shaft requires len hours to drill, where len is the length of the shaft. The shafts must be vertical, and they provide no horizontal access to adjacent pockets. We have only one drilling rig, so the two shafts cannot be drilled concurrently.

Example: if the mine is shown on the left, then you should return 5.

Mine Rescue Plan

XXXXXXXXXXXX-XXXX--- XXXX|XXXXXXX-XXXX---

XXXX-XXXXX--------XX XXXX-XXXXX--------XX

XXXXXXXXXXXXXXX--XXX XXXXXXXXXXXXXXX--XXX

XXX-XXXX----------XX XXX-XXXX----------XX

---XX---XXXXXXXXXXXX ---|X---XXXXXXX|XXXX

--------XXXXXXX--XXX --------XXXXXXX--XXX

---XXXXXXXXXXX--XXXX ---|XXXXXXXXXX--XXXX

XX-XXXXX------------ XX-|XXXX------------

XXX-------XXXXXXXXXX XXX-------XXXXXXXXXX

This mine has 4 separate air pockets (plus one which is exposed to the surface already). A solution is shown with | denoting a section of rock with a vertical shaft through it. One shaft goes from the exposed upper right pocket to the one in the lower right. Then a shaft of length 2 connects to the big pocket on the left. Notice that the vertical shaft in the next to bottom row does not provide access to the pocket on its left -- the shaft needs to be two sections long before it punches into the pocket above it. The remaining two tiny pockets are reached by shafts of length one, one down from the surface, and the other up from the left pocket.

## Deliverables

1) I need the problem solved with an efficient algorithm involving data structures so it will complete in a reasonable amount of time.

2)All lines of code must be commented. The program must be run from debug mode within Visual C++ Studio (6.0 or higher).

public class Rescue{

public int howLong(vector mine)

//pre: 1<=#mine<=50, all elements have the same length in 1..50 inclusive

each character in each string is '-' or 'X'

//post: how long it will take to reach all the pockets?

## Platform

WindowsXP, Visual C++ Studio 6.0( or equiv)

( 2 comentários ) United States

ID do Projeto: #2963939

## 5 freelancers are bidding on average \$18 for this job

mihaiscortaru

See private message.

\$16.99 USD in 5 dias
(160 Comentários)
6.0
vasilevalaiba

See private message.

\$21.25 USD in 5 dias
(9 Comentários)
2.5
vw914040vw

See private message.

\$8.5 USD in 5 dias
(16 Comentários)
1.6
dmitryakoch

See private message.

\$21.25 USD in 5 dias
(0 Comentários)
0.0
edgardlima

See private message.

\$21.25 USD in 5 dias
(0 Comentários)
0.0