Description
Introduction
The aim of this homework is to find an enclosed area in a 2D matrix that contains the characters ‘x’s and
‘o’s. Each cell on the matrix contains one letter; ‘o’ mean empty cell; ‘x’ means occupied cell or can also
be assumed as walls. User will be able to start from any coordinate and your program will automatically
find a path by going one cell at a time in vertical and horizontal directions (diagonal movement is not
allowed). At the end, depending on whether the path found is an enclosed area or not, your program should
display appropriate messages.
Two example matrices and their enclosed areas (represented via red characters) are given in Figure 1. Please
note that there also are walls that are part of an enclosed area as well.
o o o x x x x x o o o o x x x o o
o o o x o o o x o o o o x o x o o
o o o x x x x x o o x x x o x x o
x x x o o o o o o o x o o o o x x
o o x o o o o o o o x o x x x o x
o x x o o o o o o o x x x o x x x
Figure 1: Two sample matrices
Inputs, Outputs and Program Flow
First, user will be prompted for the name of the matrix file. If the file with the given name cannot be opened,
user will be prompted again until a file can successfully be opened. You must store this matrix using a 2D
matrix (i.e. a vector of vector of char or vector of vector of struct).
Once file has been opened successfully, first your program must check if there are any invalid characters
(any character different than ‘x’ and ‘o’). Then, your program must check if given matrix is a valid matrix
(i.e. same amount of characters for each row). After these input checks, first print the matrix, then user will
be asked for coordinate values, the user first enters the coordinate values of starting location (as x, for row,
and y, for column, both integers). At this point, program must handle invalid coordinates, such as reading
strings instead of integer, or out of range cases. When the user enters a valid coordinate, program will try
to find an enclosed area which starts from this coordinate. Here note that the coordinate values start with 0
both vertically and horizontally; i.e. the upper-left corner of the matrix has coordinate of (0,0). An example
case is given in Figure 2.
Figure 2: The path followed by inputs 4 3 on a sample matrix
You have to form the path by visiting one neighboring cell at a time. For this purpose, you can move to
four main directions (right, down, left and up); diagonal movements are not allowed. For this purpose, your
program should follow some pre-determined rules. First, you must not go out of matrix boundaries. Second,
a visited occupied cell must not be visited again. Another rule is that you always have to check neighbors
in the same order and this order must be Right, Down, Left and Up. When an occupied and unvisited
neighbor is found, go to that direction without checking the other remaining directions. For example, in
Figure 2, when you are currently on cell (4,4), you first try right cell (4,5), which is empty; then you try (5,
4), which is down and it is an occupied and unvisited cell, so you move there. As another example, in Figure
2, when you are currently on cell (6,2), you first try right cell (6,3), which is occupied but previously visited;
then you try down cell, which is out of boundary; then you try left cell (6,1), which is empty and finally
you try up cell (5,2), which is occupied and unvisited, so you move on that cell.
Another example matrix and two enclosed areas are given in Figure 3. As you can see there, the enclosed
area can be of any amorphous shape.
Figure 3: The path should be followed with given starting coordinates
Of course, you may not be able to find an enclosed area after forming the path as exemplified in various
cases in Figure 4. In the example on the left, the path ends up at boundary. The example in the middle is a
path that ends up without closing. The example on the right is actually a special case of having an occupied
cell with no occupied neighbor; this is not an enclosed area either.
Figure 4: Matrices with not enclosed examples
After finding a path, program should display if it is an enclosed area or not, and the followed coordinates
forming that path one by one. After displaying these necessary outputs, user should be able to enter different
coordinates until s/he enters -1 -1 to stop. Please see the sample runs for examples.
In such a program, having an occupied cell with more than two occupied neighbors may cause
complications. For example, in Figure 5, there is an enclosed area starting (0,0), but by applying the
abovementioned rules, you cannot identify this area since you get stuck at cell (2,4). In order not to
complicate this homework further and for the sake of simplicity, you can assume that all the occupied cells
in the given matrix have 0, 1 or 2 occupied neighbors. You do not need to check this case and you do not
need to resolve the issues related to the ones like in Figure 5.
Figure 5: Invalid sample matrix because of cell at (0,2) that has three occupied neighbors
Input Checks
There are a couple things you need to pay attention to when dealing with inputs, as mention before. One of
them is the given file should be a proper 2D matrix, meaning each line should contain the same number of
cells (letters). For example, if there are 5 cells in first line, every other line should also contain 5 cells. On
top of it, each cell should only contain only ‘x’ and ‘o’ characters, meaning both non-letter characters,
uppercase letters and other lowercase letters would be invalid entries. Rows may contain arbitrary number
of white characters (space, tab), you may not make any assumptions about that. You may assume there will
not be any empty lines including before, in between and after the matrix. You should control invalid
characters first, then number of the cells at each row.
Aside from matrix, the inputs for starting coordinates need to be checked. The starting coordinate should
consist of two integer values, and this coordinate should be within the limits of the matrix. If there are 𝑛
rows and 𝑚 columns in the matrix, the first coordinate entry must be between 0 and 𝑛 − 1, and the second
entry must be between 0 and 𝑚 − 1. In case of an invalid entry, you have to display an error message and
continue with taking inputs.
Sample Runs
Some sample runs are given below, but these are not comprehensive, therefore you must consider all
possible cases to get full mark. Input files are provided with the homework package.
Sample 1:
Please enter file name: matrix
Cannot find a file named matrix
Please enter file name: matrix1
Cannot find a file named matrix1
Please enter file name: matrix1.txt
Input Matrix:
o o x x x o o
o o x o x o o
o o x x x o o
o o o o o o o
o o x x x o o
o o x o x o o
o o x x x o o
Please enter starting coordinates, first row X then column Y: -2 10
Invalid Coordinates
Please enter starting coordinates, first row X then column Y: -2 -2
Invalid Coordinates
Please enter starting coordinates, first row X then column Y: ss aa
Invalid Coordinates
Please enter starting coordinates, first row X then column Y: nine
eight
Invalid Coordinates
Please enter starting coordinates, first row X then column Y: 221 999
Invalid Coordinates
Please enter starting coordinates, first row X then column Y: 2 2
Found an enclosed area. The coordinates of the followed path:
2 2
2 3
2 4
1 4
0 4
0 3
0 2
1 2
Please enter starting coordinates, first row X then column Y: -1 -1
Terminating…
Sample 2:
Please enter file name: matrix2.txt
matrix2.txt includes invalid char(s)
Sample 3:
Please enter file name: matrix3.txt
matrix3.txt is invalid matrix, does not contain same amount of char
each row!
Sample 4 (this sample run has changed on Feb. 7, 2020):
Please enter file name: matrix4.txt
matrix4.txt is invalid matrix, does not contain same amount of char
each row!
Sample 5:
Please enter file name: matrix5.txt
Input Matrix:
o o x x x o x
o o x o x o x
o o x x x o x
o o o o o o x
o o x x x o x
o o x o x o x
o o x x x o x
o o o o o o x
x x x x x x x
Please enter starting coordinates, first row X then column Y: 2 2
Found an enclosed area. The coordinates of the followed path:
2 2
2 3
2 4
1 4
0 4
0 3
0 2
1 2
Please enter starting coordinates, first row X then column Y: 5 4
Found an enclosed area. The coordinates of the followed path:
5 4
6 4
6 3
6 2
5 2
4 2
4 3
4 4
Please enter starting coordinates, first row X then column Y: 0 6
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
0 6
1 6
2 6
3 6
4 6
5 6
6 6
7 6
8 6
8 5
8 4
8 3
8 2
8 1
8 0
Please enter starting coordinates, first row X then column Y: 8 7
Invalid Coordinates
Please enter starting coordinates, first row X then column Y: 8 6
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
8 6
8 5
8 4
8 3
8 2
8 1
8 0
Please enter starting coordinates, first row X then column Y: 0 0
This cell is not occupied!
Please enter starting coordinates, first row X then column Y: -1 -1
Terminating…
Sample 6:
Please enter file name: matrix6.txt
Input Matrix:
x x x x x x x
x o o o o o x
x o x x x o x
x o x o x o x
x o x x x o x
x o o o o o x
x o x x x o x
x o x o x o x
x o x x x o x
x o o o o o x
x x x x x x x
Please enter starting coordinates, first row X then column Y: 0 0
Found an enclosed area. The coordinates of the followed path:
0 0
0 1
0 2
0 3
0 4
0 5
0 6
1 6
2 6
3 6
4 6
5 6
6 6
7 6
8 6
9 6
10 6
10 5
10 4
10 3
10 2
10 1
10 0
9 0
8 0
7 0
6 0
5 0
4 0
3 0
2 0
1 0
Please enter starting coordinates, first row X then column Y: 10 6
Found an enclosed area. The coordinates of the followed path:
10 6
10 5
10 4
10 3
10 2
10 1
10 0
9 0
8 0
7 0
6 0
5 0
4 0
3 0
2 0
1 0
0 0
0 1
0 2
0 3
0 4
0 5
0 6
1 6
2 6
3 6
4 6
5 6
6 6
7 6
8 6
9 6
Please enter starting coordinates, first row X then column Y: -1 -1
Terminating…
Sample 7:
Please enter file name: matrix7.txt
Input Matrix:
o o x x x o o o o
o o x o x o o o o
x x x o x x o o o
x o o o o x x o o
x o x x x o x o o
x x x o x x x o o
o o o o o o o x x
x x o o o o o x x
o x o x o x o o o
x x o x o x o x o
o o o x x x o o o
Please enter starting coordinates, first row X then column Y: 0 2
Found an enclosed area. The coordinates of the followed path:
0 2
0 3
0 4
1 4
2 4
2 5
3 5
3 6
4 6
5 6
5 5
5 4
4 4
4 3
4 2
5 2
5 1
5 0
4 0
3 0
2 0
2 1
2 2
1 2
Please enter starting coordinates, first row X then column Y: 4 3
Found an enclosed area. The coordinates of the followed path:
4 3
4 4
5 4
5 5
5 6
4 6
3 6
3 5
2 5
2 4
1 4
0 4
0 3
0 2
1 2
2 2
2 1
2 0
3 0
4 0
5 0
5 1
5 2
4 2
Please enter starting coordinates, first row X then column Y: 8 0
This cell is not occupied!
Please enter starting coordinates, first row X then column Y: 7 0
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
7 0
7 1
8 1
9 1
9 0
Please enter starting coordinates, first row X then column Y: 8 1
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
8 1
9 1
9 0
Please enter starting coordinates, first row X then column Y: 8 3
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
8 3
9 3
10 3
10 4
10 5
9 5
8 5
Please enter starting coordinates, first row X then column Y: 9 7
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
9 7
Please enter starting coordinates, first row X then column Y: 7 7
Found an enclosed area. The coordinates of the followed path:
7 7
7 8
6 8
6 7
Please enter starting coordinates, first row X then column Y: 7 8
Found an enclosed area. The coordinates of the followed path:
7 8
7 7
6 7
6 8
Please enter starting coordinates, first row X then column Y: 6 8
Found an enclosed area. The coordinates of the followed path:
6 8
7 8
7 7
6 7
Please enter starting coordinates, first row X then column Y: -1 -1
Terminating…
Sample 8:
Please enter file name: matrix8.txt
Input Matrix:
x x o o o o
o x o o o o
o o x x x x
o o o o o o
x x o o o o
Please enter starting coordinates, first row X then column Y: 1 1
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
1 1
0 1
0 0
Please enter starting coordinates, first row X then column Y: 0 0
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
0 0
0 1
1 1
Please enter starting coordinates, first row X then column Y: 2 2
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
2 2
2 3
2 4
2 5
Please enter starting coordinates, first row X then column Y: 2 4
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
2 4
2 5
Please enter starting coordinates, first row X then column Y: 4 0
Cannot found an enclosed area starting with given coordinate. The
coordinates of the followed path:
4 0
4 1
Please enter starting coordinates, first row X then column Y: -1 -1
Terminating…
Some Important Rules
In order to get a full credit, your programs must be efficient and well presented, presence of any
redundant computation or bad indentation, or missing, irrelevant comments are going to decrease
your grades. You also have to use understandable identifier names, informative introduction and
prompts. Modularity is also important; you have to use functions wherever needed and appropriate.
When we grade your homework, we pay attention to these issues. Moreover, in order to observe
the real performance of your codes, we may run your programs in Release mode and we may test
your programs with very large test cases. Of course, your program should work in Debug mode
as well.
What and where to submit (PLEASE READ, IMPORTANT)
You should prepare (or at least test) your program using MS Visual Studio 2012 C++. We will use
the standard C++ compiler and libraries of the abovementioned platform while testing your
homework. It’d be a good idea to write your name and last name in the program (as a comment
line of course).
Submissions guidelines are below. Some parts of the grading process might be automatic. Students
are expected to strictly follow these guidelines in order to have a smooth grading process. If you
do not follow these guidelines, depending on the severity of the problem created during the grading
process, 5 or more penalty points are to be deducted from the grade.
Name your cpp file that contains your main program using the following convention:
“SUCourseUserName_YourLastname_YourName_HWnumber.cpp”
Your SUCourse user name is your SUNet user name which is used for checking sabanciuniv emails. Do NOT use any spaces, non-ASCII and Turkish characters in the file name. For example,
if your SUCourse user name is cago, name is Çağlayan, and last name is Özbugsızkodyazaroğlu,
then the file name must be:
Cago_Ozbugsizkodyazaroglu_Caglayan_hw1.cpp
In some homework assignments, you may need to have more than one .cpp or .h files to submit.
In this case, add informative phrases after the hw number. However, do not add any other character
or phrase to the file names. Sometimes, you may want to use some user defined libraries (such as
strutils of Tapestry); in such cases, you have to provide the necessary .cpp and .h files of them as
well. If you use standard C++ libraries, you do not need to provide extra files for them.
These source files are the ones that you are going to submit as your homework. However, even if
you have a single file to submit, you have to compress it using ZIP format. To do so, first create a
folder that follows the abovementioned naming convention
(“SUCourseUserName_YourLastname_YourName_HWnumber”). Then, copy your source file(s)
there. And finally compress this folder using WINZIP or WINRAR programs (or another
mechanism). Please use “zip” compression. “rar” or another compression mechanism is NOT
allowed. Our homework processing system works only with zip files. Therefore, make sure that
the resulting compressed file has a zip extension. Check that your compressed file opens up
correctly and it contains all of the files that belong to the latest version of your homework.
You will receive zero if your compressed zip file does not expand or it does not contain the correct
files. The naming convention of the zip file is the same. The name of the zip file should be as
follows:
SUCourseUserName_YourLastname_YourName_HWnumber.zip
For example, zubzipler_Zipleroglu_Zubeyir_hw1.zip is a valid name, but
Hw1_hoz_HasanOz.zip, HasanOzHoz.zip
are NOT valid names.
Submit via SUCourse ONLY! You will receive no credits if you submit by other means (e-mail,
paper, etc.).
Successful submission is one of the requirements of the homework. If, for some reason, you cannot
successfully submit your homework and we cannot grade it, your grade will be 0.
Good Luck!
Albert Levi, Vedat Peran
