C++ problem w/ data structures

終了済み 投稿 Aug 15, 2003 着払い
終了済み 着払い

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).

3) Please use-------

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)

C プログラミング エンジニアリング MySQL PHP ソフトウェアアーキテクチャ ソフトウェアテスト

プロジェクトID: #2963939

プロジェクトについて

5個の提案 リモートプロジェクト アクティブ Sep 15, 2003

5人のフリーランサーが、平均$18 で、この仕事に入札しています。

mihaiscortaru

See private message.

$16.99 USD 5日以内
(160件のレビュー)
6.0
vasilevalaiba

See private message.

$21.25 USD 5日以内
(9件のレビュー)
2.5
vw914040vw

See private message.

$8.5 USD 5日以内
(16件のレビュー)
1.6
dmitryakoch

See private message.

$21.25 USD 5日以内
(0件のレビュー)
0.0
edgardlima

See private message.

$21.25 USD 5日以内
(0件のレビュー)
0.0