---
tags: 2023DS
---
# 2023 Data Structure - Homework 3: Maze
* Deadline: 4/14 - 14:00
* Upload your homework to **moodle** platform.
* Please consult with TA if you have any questions.
* FB or email
## Problem
In the given input maze file (```p3.in```), 0's are available path and b's are blocked.
Your homework is to use all the codes provided in the textbook, including **the template for the stack** class and **the path function** to write your C++ codes, in order for the rat to find the route out of the maze. It is important that you fully understand each piece of the codes provided in the text before writing your code. After completing the coding, write down what you learn or any discussions from this exercise, as well.
Chapter 3 slide (p.9~p.10) provides the referenced code, you can refer the slide to complete the stack class.
## Input file description
Input matrix-like symbols separated by a space, there are 4 type of symbol: s, b, e and 0. The rat **begins at the s position** and **exit in e position**, symbol **b means the path is not available**, 0 means the path is available.
There’s no pre-defined size variables (e.g. n, m), so that the program should **be dynamic**, not static size. Each line has the same number of symbols.
## Output file description
Print out the path found, if any, by marking the positions using the following symbol defined for the path in the maze. For example, assuming you are given a 4×5 maze whose entrance is (0, 0) and exit is (3,4), then your output file may show the path as follows:
## Sample Input
```
s 0 0 b 0
b b 0 b 0
0 b 0 b b
0 b b 0 e
```
## Sample Output
```
s - - b 0
b b | b 0
0 b | b b
0 b b \ e
Total 6 Steps.
```
:::info
Hint:
```-```: walk **horizontally**
```|```: walk **vertically**
```/``` or ```\```: walk **obliquely**
For each test case, it may have several answers, **and you just print out a correct answer.**
:::
## Restriction
**C++ STL containers**, such as ```<stack>```, ```<vector>```... , **are forbidden** for this homework.
## Note
Compress all the files (including your report and source code files), and name the compressed file as ```A1095500_hw3.zip(or .rar)``` using your student ID. Then upload the compressed file to the **moodle** platform.
Also, **TA will provide some test cases** (***.in**), and you shall print out the output in the ***.out** after executing your binary executable.
The file structure should be like following forms:
```
|-A1105500_hw3.zip (.rar)
| |-main.cpp
| |-xxx.h
| |-xxx.cpp
| |-Report.pdf
| |-(And other files...)
```
or
```
|-A1105500_hw3.zip (.rar)
| |-A1105500 (Folder)
| | |-main.cpp
| | |-xxx.h
| | |-xxx.cpp
| | |-Report.pdf
| | |-(And other files...)
```
**Don't cheating**, or you will get 0 for this homework. If you can’t finish this homework before deadline, just hand in your unfinished code and report.
**Be honest with yourself.**
## Score
* Source code: 70%
* test*.out: 5% per file
* Report: 15%
## [Must] Test cases
You can go to moodle platform to get the ```hw3-testcase.zip``` file.
There are three test cases that you need to solve, and you shall print out the output in the **test\*.out** file!
e.g., If you run the ```test1.in```, you need to redirect your output to the file ```test1.out```.
---
* Go to moodle platform to download the test cases!
---
Sign in with Wallet
Connect another wallet