首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
ECE2810J代做、代写C++语言编程
项目预算:
开发周期:
发布时间:
要求地区:
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
You should replace
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
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
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
代做 program、代写 c++设计程...
2024-12-23
comp2012j 代写、代做 java 设...
2024-12-23
代做 data 编程、代写 python/...
2024-12-23
代做en.553.413-613 applied s...
2024-12-23
代做steady-state analvsis代做...
2024-12-23
代写photo essay of a deciduo...
2024-12-23
代写gpa analyzer调试c/c++语言
2024-12-23
代做comp 330 (fall 2024): as...
2024-12-23
代写pstat 160a fall 2024 - a...
2024-12-23
代做pstat 160a: stochastic p...
2024-12-23
代做7ssgn110 environmental d...
2024-12-23
代做compsci 4039 programming...
2024-12-23
代做lab exercise 8: dictiona...
2024-12-23
热点标签
mktg2509
csci 2600
38170
lng302
csse3010
phas3226
77938
arch1162
engn4536/engn6536
acx5903
comp151101
phl245
cse12
comp9312
stat3016/6016
phas0038
comp2140
6qqmb312
xjco3011
rest0005
ematm0051
5qqmn219
lubs5062m
eee8155
cege0100
eap033
artd1109
mat246
etc3430
ecmm462
mis102
inft6800
ddes9903
comp6521
comp9517
comp3331/9331
comp4337
comp6008
comp9414
bu.231.790.81
man00150m
csb352h
math1041
eengm4100
isys1002
08
6057cem
mktg3504
mthm036
mtrx1701
mth3241
eeee3086
cmp-7038b
cmp-7000a
ints4010
econ2151
infs5710
fins5516
fin3309
fins5510
gsoe9340
math2007
math2036
soee5010
mark3088
infs3605
elec9714
comp2271
ma214
comp2211
infs3604
600426
sit254
acct3091
bbt405
msin0116
com107/com113
mark5826
sit120
comp9021
eco2101
eeen40700
cs253
ece3114
ecmm447
chns3000
math377
itd102
comp9444
comp(2041|9044)
econ0060
econ7230
mgt001371
ecs-323
cs6250
mgdi60012
mdia2012
comm221001
comm5000
ma1008
engl642
econ241
com333
math367
mis201
nbs-7041x
meek16104
econ2003
comm1190
mbas902
comp-1027
dpst1091
comp7315
eppd1033
m06
ee3025
msci231
bb113/bbs1063
fc709
comp3425
comp9417
econ42915
cb9101
math1102e
chme0017
fc307
mkt60104
5522usst
litr1-uc6201.200
ee1102
cosc2803
math39512
omp9727
int2067/int5051
bsb151
mgt253
fc021
babs2202
mis2002s
phya21
18-213
cege0012
mdia1002
math38032
mech5125
07
cisc102
mgx3110
cs240
11175
fin3020s
eco3420
ictten622
comp9727
cpt111
de114102d
mgm320h5s
bafi1019
math21112
efim20036
mn-3503
fins5568
110.807
bcpm000028
info6030
bma0092
bcpm0054
math20212
ce335
cs365
cenv6141
ftec5580
math2010
ec3450
comm1170
ecmt1010
csci-ua.0480-003
econ12-200
ib3960
ectb60h3f
cs247—assignment
tk3163
ics3u
ib3j80
comp20008
comp9334
eppd1063
acct2343
cct109
isys1055/3412
math350-real
math2014
eec180
stat141b
econ2101
msinm014/msing014/msing014b
fit2004
comp643
bu1002
cm2030
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!