# C代写 | C++代写 |算法代写| 数据结构代写 | data structures代写 – Data Structures Battleship Recursion

C代写 | C++代写 | 数据结构代写 | data structures代写 : 这是一个典型的C++相关的数据结构的作业代写，难度相当大，对个人在数据结构方面的理解要求很高，对C++的水平也有较高的要求
In this homework we will solve ship placement puzzles inspired by the pencil & paper “Battleship” game that
was later made into a board game by Milton Bradley and then a puzzle that is a regular feature in Games
magazine. You can read more about the history of the game and see examples here:
https://en.wikipedia.org/wiki/Battleship_(game)
https://en.wikipedia.org/wiki/Battleship_(puzzle)
This is a popular game with lots of material available online. You may not search for, study, or use any code
related to the Battleship game or puzzle. Please carefully read the entire assignment and study the examples
Battleship Puzzles – How to Play
Your program will accept one or two command line arguments. The first argument is the name of a battleship
puzzle board file similar to the file shown below. This sample file begins with the dimensions of the board,
in this case 4 rows and 5 columns. Next, we give the number of cells in each row and each column that are
occupied by a ship. The other cells in the row are open water. Then, we have a simple list of the ships that
must be placed on that board. All ships are 1 cell wide, but each ship type has a different length (# of cells):
submarine = 1, destroyer = 2, cruiser = 3, battleship = 4, carrier = 5, cargo = 6, and tanker = 7.
board 4 5
rows 4 0 2 1
cols 1 2 1 2 1
cruiser
destroyer
submarine
submarine
4
1 2 1 2 1
1
2
0
Your task is to place the ships on the board satisfying the counts for each row. One important rule in
placing the ships is that no two ships may occupy adjacent cells (including the diagonal). The sample puzzle
above actually has two solutions. The diagram and sample output below show one of the solutions. Can you
manually find the other?
Solution:
cruiser 0 0 horizontal
submarine 0 4
submarine 2 1
destroyer 2 3 vertical
+—–+
| o|4
| |0
| o ^ |2
| v |1
+—–+
12121
1
2
0
4
1 2 1 2 1
Output Formatting
To ensure full credit on the homework server, please format your solution exactly as shown above. The
solution must begin with the keyword “Solution:”, followed by a line for each ship beginning with the ship
type, the row and column of the upperleftmost cell occupied by the ship, and for non-submarine ships the
orientation of the ship (“horizontal” or “vertical”). The ships may be listed in any order. After the ship
placement details, you should make an ASCII art diagram of the solved board (this will help in debugging).
However, this will be graded by the TAs not the automated grading on the homework server, so you may
format your ASCII art diagram somewhat differently than the sample above.
If the optional second argument find_all_solutions is not specified, your program should output to
std::cout any single valid solution to the puzzle. If the optional argument find_all_solutions is specified,
your program should output all valid, unique solutions (in any order) and then also print at the bottom
the number of solutions found, e.g., “Found 2 solution(s)”. If the puzzle has no solutions, your program
should print “No solutions”. When searching for all solutions, make sure you do not double count or duplicate
the same solution. For example, if a puzzle has two submarines, swapping the submarines does not
make a “new” solution.
Puzzles with Cell Constraints
Some input puzzle files have one or more additional constraints placed on some of the cells. These will be
listed in the input file after the ships. Here is an example:
board 4 5
rows 4 0 2 1
cols 1 2 1 2 1
cruiser
destroyer
submarine
submarine
constraint 0 2 < 1 2 0 4 1 2 1 2 1 Each constraint line begins with the keyword “constraint”, then the row and column, then one of 7 characters: ’o’ to represent a submarine; ’<’ or ’>’, to represent the left or right cells of a horizontal ship
(length ≥ 2); ’^’, or ’v’, to represent the top or bottom cells of a vertical ship (length ≥ 2); ’X’ to represent
a middle cell (not either end) of a ship with length ≥ 3; or ’_’ to represent open water. Your task is to limit
the output to solutions that match these constraints.
Puzzles with Unknown Sums and/or Unknown Ship Types
The final twist for this assignment is that the input file may have some unspecified row and/or column sums
(listed as ’?’) and/or some ships of unspecified type (listed as “unknown”), which may be any length from 1
to 7 cells. Here is an example input:
board 4 5
rows ? 0 2 1
cols 1 2 1 ? 1
cruiser
destroyer
submarine
unknown
time battleship.out puzzle_sample.txt find_all_solutions > out_puzzle_sample_all.txt
• You may want to use a C++ code profiler to measure the efficiency of your program and identify the
portions of your code that consume most of the running time. A profiler can confirm your suspicions
about what is slow, uncover unexpected problems, and focus your optimization efforts on the most
inefficient portions of the code.
• We will be testing with and without the optional command line argument find_all_solutions and
will highlight the most correct and the fastest programs.
• You may submit up to two interesting new test cases for possible inclusion in the contest. Name these
tests smithj_1.txt and smithj_2.txt (where smithj is your RCS username). Extra credit will be
awarded for interesting test cases that are used in the contest. Caution: Don’t make the test cases so
difficult that your program cannot solve them in a reasonable amount of time!
• In your README_contest.txt file, describe the optimizations you implemented for the contest, describe
your new test cases, and summarize the performance of your program on all test cases.
• Extra credit will be awarded based on overall performance in the contest.
3