Homework 1 Finding Enclosed Area in a Matrix Solution

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 o x o o o x o o

o o o x x x x x o o

x x x o o o o o o o

o o x o o o o o o o

o x x o o o o o o o



o o x x x o o

o o x o x o o

x x x o x x o

x o o o o x x

x o x x x o x

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:

Please enter file name: matrix4.txt matrix4.txt includes invalid char(s)


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 e-mails. 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