Homework 4 Area Filling using Stacks Solution

In this homework, you are asked to implement an area filling program which makes use of stack data structure. Area filling is the process of filling a connected and closed area in a map with a given value (color or a filling character). The map is a 2D array with solid boundary and some occupied cells within itself. A connected and closed area in this map contains consecutive empty cells surrounded by the boundary and/or occupied cells. Such an area can be of any shape (including amorphous shapes). In the program that you will write, the user will enter a coordinate of an empty cell of an area in the map. After that, your program should fill all the empty cells in the corresponding area with a filling character. The details of the methods, algorithms and the data structure will be given in the subsequent section of this homework specification.

General idea of area filling

In this section, we will explain the general idea of area filling via some examples. An example of a map which has 11 rows and 9 columns can be seen in Figure 1 below. In this homework, we assume that the map is of rectangular shape and there is a boundary around it.
0    1    2    3    4    5    6    7    8

0

1

2

3

4

5

6

7

8

9

10

Fig 1. An example map

A map can have any number of connected and closed areas. In the map of Figure 1, there are four areas of different shapes and different numbers of cells. In order to fill an area, the user will enter a starting coordinate of an empty cell in that area. For example, let us assume that (2, 5) is given as the starting point. If the starting point is empty, your program must fill the connected and closed area which contains this point. The point (2, 5) is empty in the given example. For the sake of simplicity of explanation, let us fill this area with blue (in the actual program you will use character filling). The resulting filled map can be seen in Figure 2.

















Fig 2. An example result

Instead of (2, 5), if the user chooses to start from (7, 6), the result must be like in Figure 3.

















Fig 3. An example result

Here please remark that the program that you will implement will use ASCII characters for borders, occupied cells and filling. The details of the data structure and input/output will be given in the next sections.
Input and output

Firstly, the program asks the number of rows and columns of the map (first number of rows and then number of columns). Here, you need to check if these values are positive integers that are greater than or equal to 3; if not, your program should display an error message and then ask for a new input until values that are greater than or equal to 3 have been entered. Then, your program asks the name of the file which includes the map with the given number of rows and columns. Coordinates begin with zero for both rows and columns. You can assume that the file has data for a correct rectangular map in terms of row and column counts entered by the user. You can also assume that the map has a boundary around it. However, the boundary is also counted in the numbers of rows and columns. You do not need to make an input check for the file content, but you should check whether the file exists; if it does not, then your program should ask for a new file name until file is opened successfully.

After reading map from the file, in order to fill an area in this map, a starting point is entered from the keyboard. This input consists of two values: row and column coordinates (you have to read first row and then column). These values must be within the range of the matrix. If not, your program should repeatedly ask for them until valid values are entered. Moreover, the starting point must be empty. If the entered starting point is occupied, then your program should not perform filling and terminate after giving a message. The connected and closed area is filled with a character taken from the user as input from the keyboard. The filling character should not be ‘X’ or 'x'. If an invalid filling character is entered, it must be repeatedly entered until user enters a valid one. See sample runs for example cases.

We know the limitations of the console and printable characters. Therefore, in the text file, non-empty cells in the map are represented with 'X'. On the other hand, empty cells are blank character, ' '. Since it is not possible to fill a text file with colors, we fill it with a character taken from the user as input. The text file version of the example given in Figure 1 can be seen below in Figure 4.

XXXX
XXXXX
X


X   X
X
X
X
X X X
XXXX

X
X
X
XXXX
X X
X
X X
X
X

X
X
X
X X
X X
X
X
X
X
X X
X

X
X X X
XXXX
XXXXX

Fig 4. An example text file

If we fill the area with character 'O' and the starting point is (2, 5), the result must be like in Figure 5.

XXXXXX
X X X
XOOOOO
X   X
XOOXXO
X X X
XXXXOO
O O X
X
X O X
X X X
X X
X X X
X
X
X
X
X  XXXX
X
X   X
X
X X
X
X
X X X
XXXXXX
X X X

Fig 5. An example result
If we fill the area with character “s”, and the starting point is (7, 6), the result must be like in Figure 6.

XXXX
XXXXX
X

X   X
X
X
X  XXX
XXXX
X
    X X XXXX X X X X X s s X

X X s s s X X X X X X s s X X X X s s X X
XX s X X X
XXXXXXXXX

Fig 6 An example result


Data structures used

The map is actually a character matrix. In your program, you will create a dynamic char matrix, without using vector class, to store the characters in the map.

Another data structure that you will use is a stack. As will be discussed in the next section, in order to keep track of visited cells while scanning the area, you must use a stack data structure. The data that you will keep in each element of this stack are row and column coordinates of a cell in the map. We are expecting you to implement a dynamic stack class for this application and use it in the main program. The dynamic stack class that you will implement must contain only push, pop, and isEmpty member functions other than the standard ones (constructor, destructor, deep copy constructor and assignment operator). In other words, you are not allowed to add extra public member functions that violate the spirit behind stack (i.e. a member functions such as to display the content, check the top element without popping, insert in the middle, etc. are NOT allowed). If some helper functions are needed (e.g. createClone), define them as private and use only in the member function implementations. In the program part, that you will fill the area of the map, your programmer's interface will only be classical stack operations (constructor, copy constructor,

    • operator, destructor, push, pop, and isEmpty). Actually, you may not want to implement deep copy constructor and assignment operator if you do not need (this is up to you). However, you must write a constructor and a destructor for your dynamic stack class. During the implementation of class member functions, you can (actually have to) use linked lists.

You are not allowed to use any other container in this homework.

Algorithmic details and hints

Since it may not be so clear to you how to scan an area of an amorphous shape, we give some algorithmic hints in this section. The main idea of the algorithm that you will use is to keep track of all visited cells (by pushing them onto the stack) and backtrack to the previously visited cell (by popping from the stack) when you are stuck.

You have to start from the starting coordinate and fill it with the filling character. After that you have to move towards an empty neighbor in one of four directions (north, east, south, west). Crosswise neighbors are not taken into consideration. If you can move in one of those directions, first remember the current cell (using stack), and then move. When you move to this neighbor, fill it and do the same until you are stuck (i.e. no empty neighbors). If you are stuck, you have to go back (using stack) and try to find an available cell with an empty
neighbor. When you backtrack to such a cell, continue as above. If you follow this algorithm properly, when you fill all the cells in an area, the stack must be empty.

At the end, your program must display the resulting filled map to the screen.

There also exist recursive solutions to the area filling problem. However, we strongly recommend you not to use recursion for this problem. If you use recursion for area filling problem, at each function call you can make as much as four recursive calls (one for each direction). For some big (actually not so big) maps, these recursive calls cause to use up all available memory and your program crashes. If you write your code recursively and if your recursive program does not work with our grading cases, we do not take any responsibility.


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. Since using classes is mandated in this homework, a proper object-oriented design and implementation will also be considered in grading.

Since you will use dynamic memory allocation in this homework, it is very crucial to properly manage the allocated area and return the deleted parts to the heap whenever appropriate. Inefficient use of memory may reduce your grade.

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.

You are allowed to use sample codes shared with the class by the instructor and TAs. However, you cannot start with an existing .cpp or .h file directly and update it; you have start with an empty file. Only the necessary parts of the shared code files can be used and these parts must be clearly marked in your homework by putting comments like the following. Even if you take a piece of code and update it slightly, you have to put a similar marking (by adding "and updated" to the comments below.

/* Begin: code taken from ptrfunc.cpp */

…

/* End: code taken from ptrfunc.cpp */
Sample runs

Some sample runs are given below, but these are not comprehensive, therefore you have to consider all possible cases to get full mark. Please do not make any assumptions on the names of files.

Sample run 1:
File: 11x12.txt


This is to show
the content of the

file for your
convenience; do
not display it like
that in your

program


---------




XXXXXXXXXXXX
X
X

X X
X
X

X X
X
X X
X
X
X
X X
X X
X
X
X  XXX
X
X
XXXX
X
X
X X
X X

X X
X
XXXXXXXX
X


X

XXXXXXXXXXXX


Enter the number of rows: -1000
-1000 is not valid!
Enter the number of rows: 0

0 is not valid!
Enter the number of rows: 2

2 is not valid!
Enter the number of rows: ASD
ASD is not valid!

Enter the number of rows: 11
Enter the number of columns: -1000

-1000 is not valid!
Enter the number of columns: 0
0 is not valid!

Enter the number of columns: 2
2 is not valid!
Enter the number of columns: ASD
ASD is not valid!
Enter the number of columns: 12

Please enter file name: 11x12
Cannot open a file named 11x12
Please enter file name: 11x12.txt
Enter the starting point: ASD ASD
Invalid coordinate!

Enter the starting point: 1 ASD
Invalid coordinate!
Enter the starting point: ASD 1
Invalid coordinate!
Enter the starting point: -1 10

Invalid coordinate!
Enter the starting point: -1 ASD

Invalid coordinate!
Enter the starting point: 11 12
Invalid coordinate!

Enter the starting point: 10 11

Starting point is already occupied.

Terminating...
Sample run 2:
File: 11x12.txt



This is to show the content of the file for your convenience; do not display it like that in your program



-----




XXXXXXXXXXXX
X
X

X X
X
X

X X
X
X X
X
X
X
X X
X X
X
X
X  XXX
X
X
XXXX
X
X
X X
X X

X X
X
XXXXXXXX
X


X

XXXXXXXXXXXX


Enter the number of rows: 11

Enter the number of columns: 12

Please enter file name: 11x12.txt
Enter the starting point: 1 1
Enter the filling char: x
Filling char is not valid!
Enter the filling char: X
Filling char is not valid!
Enter the filling char: O

XXXXXXXXXXXX

XOOOOX    XX
XOOOOX    XX
XOOOXX    X    X

XOOXX    XX    X
XOOOX XXX    X

XOOXXXX X    X
XXOXX    XX
XOOOXXXXXXXX

XOOOOOOOOOOX
XXXXXXXXXXXX

Sample run 3:
File: 22x40.txt
This is to show the content of the

file for your convenience; do not

display it like that in your program

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

X




XXXX
X




X X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXX
XXXXX
XXXXXXXX
X X X
X
X X



XXXXX
XXXXX
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXX
X X
XXXXX
XXXXXXXX

X
X





X
X





X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X
XXXXXXXX


X X
X
XXXXXXXXXXXXXXXXXXXXX
XXXX
XXXXXXXXX


XXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXX




X
X



X X X

X
X





X
X  X X
X

X  X  X
X  X  X
X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
------





Enter the number of rows: 22




Enter the number of columns: 40



Please enter file name: 22x40.txt



Enter the starting point: 100 100



Invalid coordinate!




Enter the starting point: -1 -1



Invalid coordinate!




Enter the starting point: 2 38



Enter the filling char: M




XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


X



XXXX


X



XXMX


XXXXXXXXXXXXXXXXXXXXXXXXX

XXXX


XXXXX

XXXXXXXX
XXX
X


XX

XXXXX

XXXXX


XXXXXXXXXXXXXXXXXXXX
XXXXXXXXX


XX
XXXXX
XXXXXXXX

X


X



X


X



X



    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX  X
XXXXXXXX


XX
X
XXXXXXXXXXXXXXXXXXXXX
XXXX
XXXXXXXXX


XXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXX



X
X

XXX

X
X



X
X XX
X
X X X
X X X
X

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Sample run 4:
File: 22x40.txt
This is to show the content of the

file for your convenience; do not

display it like that in your program

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

X    XXXX
X    X X    X
XXXXXXXXXXXXXXXXXXXXXXXXX    XXXX
XXXXX    XXXXXXXX    XXX    X
XX    XXXXX    XXXXX
XXXXXXXXXXXXXXXXXXXX    XXXXXXXXX
XX    XXXXX    XXXXXXXX    X
X    X

X X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X

XXXXXXXX    XX    X
XXXXXXXXXXXXXXXXXXXXX    XXXX

XXXXXXXXX XXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXX    X
X    XXX    X
X    X

XXX X XXX XXX X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


-----

Enter the number of rows: 22
Enter the number of columns: 40

Please enter file name: 22x40.txt
Enter the starting point: 12 20
Enter the filling char: I

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

X



XXXX
X



XX X
XXXXXXXXXXXXXXXXXXXXXXXXX

XXXX
XXXXX

XXXXXXXX
XXX
X
XX

XXXXX

XXXXX
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXX
XX
XXXXX
XXXXXXXX

X
X



X
X



X

    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X XXXXXXXXIIIIIIIIIIIIIIIIIIIIIIIIIIIXX X XXXXXXXXXXXXXXXXXXXXXIIIIIIIIIIIIIIIXXXX XXXXXXXXXIIIIIIIIIIIIIIIIIIIIIIIXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXX




X
X

XXX


X
X




X
X XX
X
X X
X
X X X
X

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX



Sample run 5:
File: 34x51.txt



XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


X
X


X
X


X
X


X
X


X
X


X
X
This is to show





X
X
the content of the

X
X
file for your

X
X
convenience; do

X
X
not display it like

X
X
that in your





X
X
program





X
X






X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


X
X


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
-----





Enter the number of rows: 34

Enter the number of columns: 51
Please enter file name: 34x51.txt
Enter the starting point: 16 25

Enter the filling char: Q

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX

XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX

XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX
XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Sample run 6:
File: 3x10.txt


This is to show the content of the file for your convenience; do not display it like that in your program


-----





XXXXXXXXXX

    X X XXXXXXXXXX

Enter the number of rows: 3

Enter the number of columns: 10

Please enter file name: 3x10.txt

Enter the starting point: 1 4
Enter the filling char: /

XXXXXXXXXX
X////////X
XXXXXXXXXX

Sample run 7:
File: 3x10.txt






This is to show the content of the file for your convenience; do not display it like that in your program





-----

Enter the number of rows: 10
Enter the number of columns: 3

Please enter file name: 10x3.txt
Enter the starting point: 5 1
Enter the filling char: \

XXX

X\X
X\X
X\X
X\X
X\X

X\X
X\X

X\X
XXX





XXX

    X X X X X X X X X X X X X X X X XXX





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_hw4.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_hw4.zip is a valid name, but

Hw4_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