ECE2810J代做、代写C++语言编程

日期：2024-11-23 10:43

ECE2810J — Data Structures

and Algorithms

Programming Assignment 3

— UM-SJTU-JI (Fall 2024)

Notes

• Submission: on JOJ

• Due at Dec 1st, 2024, by 23:59

1 Introduction

In this assignment, you are tasked with implementing a C++ solution to a simpliffed version of the “sokoban” game,

where the objective is to push speciffc boxes to designated target positions on a grid. The challenge lies in devising an

efffcient strategy to navigate the grid, avoid obstacles, and ensure that all required boxes reach their target locations.

Your program should be able to handle various conffgurations of boxes, walls, and goals, ensuring the correct boxes are

pushed to their intended destinations. This project is C++ only, no other language is allowed.

2 Programming Assignment

2.1 Read Map

The map is designed as a grid where each cell is either a walkable path, a wall, or a point of interest (like the starting

point or a box). The ffrst line of the ffle deffnes the dimensions of the map in terms of columns and rows. The rest of

the ffle speciffes the content of each cell in the grid, using a series of symbols to represent different elements:

• . - Path: This represents a walkable path where the player can move freely. Boxes can also be pushed across

this type of cell.

• # - Wall: This represents an impassable barrier. Neither the player nor the boxes can pass through these cells.

• S - Starting Point: This is where the player begins. Each map should contain exactly one S character.

• B - Box’s Original Position: The initial position of a box.

• T - Target Position for Boxes: The destination cell for a box.

• R - Box at Target Position: This indicates that a box has been successfully pushed to its target position.

To ensure a valid and challenging map, the following constraints must be met:

(1) The outermost boundary of the map must be composed entirely of walls (#) to prevent the player or boxes from

exiting the map area.

(2) Each map must contain exactly one starting point (S).

(3) For test cases of the ffrst part on JOJ, the number of boxes (B) will be less or equal to 8 and the result of rows

times columns should be less or equal to 800.

(4) For test cases released on Canvas, it can be very complicated.

The player can move in four cardinal directions:

• Up

1• Down

• Left

• Right

The player can push a box if it is adjacent in one of these directions, and if the cell behind the box in that direction is

a path (.). Boxes can only be pushed. In other words, they cannot be pulled. Only one box can be pushed at a time,

and the player must move to the former box’s position after pushing it.

Below is an example of a map conffguration ffle. In this example, the map size is speciffed on the ffrst line as 11 10,

indicating 10 rows and 11 columns. The outer boundary is composed of walls (#), while inner cells deffne paths, the

starting point, box positions, and target positions.

11 10

###########

#..#..#...#

#..B....#.#

#..##.#...#

##.#...B###

##.#.....##

#SBBTT#..##

#..#.TT.###

####..#####

###########

2.2 Search routes

Help the player to ffnd the shortest route to push all the boxes to the expected place. Please notice that it is possible

that there are multiple boxes and multiple target positions. The player should push all the boxes to the target positions.

2.3 Show the route

The task requires the program to display the player’s route on the map, detailing each movement step-by-step. Each

step should be represented by a character indicating the direction moved:

• U for up

• R for right

• L for left

• W for down

For instance, given the map conffguration shown, the route may look like:

DRURRUURUURRDDDLLLDDRRRURULLLDLDRULLLUUULUURDRRURDDDDDLLLUUULURRRURDDDDULD

This format will be used as the return value of the solve function provided in the template code.

Bonus Requirements

(1) Display the map, player, boxes, and other elements at each step using the same format as the input map. Store

all the map state in a ffle, ensuring it is clear and easy to read.

2(2) Use a graphical interface to visually represent each step, showing the map, player, boxes, and other elements in

their updated positions. The output should be displayed as an animation, with each step shown for a brief period

before transitioning to the next step.

2.4 Unsolvable Maps

In some cases, a map conffguration may be unsolvable due to the positioning of walls or boxes, creating an impasse

that prevents the player from reaching all targets. Such conffgurations are referred to as “invalid maps.” This occurs

when one or more boxes are placed in positions from which they cannot be moved to their designated target cells.

A map is considered invalid if:

• There is more than one starting point or no starting point.

• There are more boxes than target positions.

• A box is surrounded by walls or other boxes in a way that makes it immovable.

• Any box is placed in a corner or against a wall where it has no path to the target position.

The following example demonstrates a typical invalid map layout:

11 10

###########

#..#..#...#

#.#B....#.#

#..##.#...#

##.#....###

##.#.....##

#S..TT#..##

#..#.TT.###

####..#####

###########

In this map: The box (B) is located next to walls on two sides, which prevents it from being moved toward the target

position (P).

When the program encounters such a conffguration, it should recognize the situation as unsolvable and output a

message as “No solution!” The program should then terminate without attempting to ffnd a solution or display a route.

3 Input / Output

As mentioned above, the input map is stored in a ffle. To test your program, you can use the following command to

read the map from a ffle:

1 ./main < inputMap.txt

For submission on JOJ, the output (i.e. the return value of the function) should either be “No solution!” or the route

to push all the boxes to the target positions.

If you have implemented the ffrst bonus requirements, you should ffrst display the steps in the format mentioned above,

and then display the map at each step. We highly recommend you to store the map at all steps in a ffle. For example,

if the output is stored in a ffle named output.txt, you can use the following command:

31 ./main < inputMap.txt > output.txt

If you have implemented the second bonus requirements, you should display the map in a graphical interface.

4 Submission

(1) For part 1 on JOJ, submit your source code in one ffle named sokoban.hpp. Your source code should include a

function named solve and a function named read_map.

(2) For part 2 on JOJ, put the detailed route output in the answers part in sokoban.hpp. The test cases will be

released on canvas, which may take a long time for your program to run. Please notice that part 2 and bonus

will be graded if and only if you can pass 80 percent of the test cases in part 1.

(3) Submit the source code on Canvas along with a corresponding Makefile to compile the source code. A sample

Makefile is provided on Canvas, which you may modify as needed. Your code submitted on Canvas should be

able to compile successfully and output the detailed route with the corresponding input ffle.

(4) (Optional) If you have implemented the ffrst bonus requirement, you also need to submit the output ffles on

Canvas. The naming format should match the original ffle name. For example, if the input ffle is named big_1.in,

the output ffle should be named big_1_detail.out. Failure to follow the correct naming format will result in

an invalid submission.

(5) (Optional) If you have implemented the second bonus requirement. You may come to the TA’s offfce hours

to demonstrate your program. The due date will be the same. The TA will give you a score based on the

demonstration.

5 Implementation Requirements and Restrictions

5.1 Requirements

• You must make sure that your code compiles successfully on a Linux operating system with g++ and the options

-std=c++1z -Wall -Wextra -Werror -pedantic -Wno-unused-result -Wconversion -Wvla.

• You can use any header ffle deffned in the C++17 standard. You can use cppreference as a reference.

5.2 Memory Leak

You may not leak memory in any way. To help you see if you are leaking memory, you may wish to call valgrind, which

can tell whether you have any memory leaks. (You need to install valgrind ffrst if your system does not have this

program.) The command to check memory leak is:

valgrind --leak-check=full <COMMAND>

You should replace <COMMAND> with the actual command you use to issue the program under testing. For example, if

you want to check whether running program

./main < input.txt

causes memory leak, then <COMMAND> should be “./main < input.txt”. Thus, the command will be

valgrind --leak-check=full ./main < input.txt

45.3 Code Quality

We will use cpplint, cppcheck to check your code quality. If your code does not pass these checks, you will lose some

points.

For cpplint, you can use the following command to check your code quality:

1 cpplint --linelength=120

,→ --filter=-legal,-readability/casting,-whitespace,-runtime/printf,

2 -runtime/threadsafe_fn,-readability/todo,-build/include_subdir,-build/header_guard

,→ *.h *.cpp

For cppcheck, only things related to error will lead to deduction. You can use the following command to check your

code quality:

1 cppcheck --enable=all *.cpp

6 Grading

6.1 Correctness

We will use the test cases on JOJ and Canvas to verify the correctness of your code. This section will have a total

score of 100 points.

6.2 Code Quality

Bad code quality will lead to a deduction of up to 20 points.

6.3 Bonus

For the ffrst bonus requirement, you can get up to 10 points. For the second bonus requirement, you can get up to

30 points. Please notice that bonus will be graded if and only if all the small test cases are passed. What’s more, the

total score will not exceed 130 points.

7 Late Policy

Same as the course policy.

8 Honor Code

Please DO NOT violate honor code.

Some behaviors that are considered as cheating:

• Reading another student’s answer/code, including keeping a copy of another student’s answer/code

• Copying another student’s answer/code, in whole or in part

• Having someone else write part of your assignment

• Using test cases of another student

5• Testing your code with another one’s account (Testing chances are limited)

• Post your code to github

9 Acknowledgement

This programming assignment is designed based on ENGR1510J Lab 3.

6