Starting from:
$30
CS204-Homework 1 Finding Enclosed Area in a Matrix Solved
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...
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...
1 file (3.9MB)
