Starting from:
$30
CS204-Homework 4 Area Filling using Stacks Solved
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.
XXXXXXXXX X X X
X XX XXX
XXXX X
X X XXXX
XX XXX X X X X
X XXXX X
X X X XX
X X XXX
XXXXXXXXX
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.
XXXXXXXXX
XOOOOOX X XOOXXOXXX XXXXOOOOX
X XOXXXX XX XXX X X X X
X XXXX X X X X XX
X X XXX XXXXXXXXX
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.
XXXXXXXXX
X X X X XX XXX
XXXX X
X X XXXX
XX XXXssX
X XsssX
X XXXXssX X X XssXX X XsXXX
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.
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
XXXXXXXXXXXX
This is to show X X XXX X XX the content of the X XX X X file for your X XX XX X convenience; do X X XXX X not display it like X XXXX X X that in your XX XX XX program 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 XX X X XX
X XX X X X XX XX X X X XXX X
X XXXX X X XX XX XX 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
This is to show the content of the file for your convenience; do not display it like that in your program
Sample run 3:
File: 22x40.txt
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X XXXX
X XX X
XXXXXXXXXXXXXXXXXXXXXXXXX XXXX XXXXX XXXXXXXX XXX X
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
XX XXXXX XXXXX
XXXXXXXXXXXXXXXXXXXX XXXXXXXXX
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
This is to show the content of the file for your convenience; do not display it like that in your program
Sample run 4:
File: 22x40.txt
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
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
-----
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
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 X X X X
X X
X X
X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
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: 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
XXX
X X
X X
X X
X X
X X
X X
X X
X X
XXX
-----
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
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.
XXXXXXXXX X X X
X XX XXX
XXXX X
X X XXXX
XX XXX X X X X
X XXXX X
X X X XX
X X XXX
XXXXXXXXX
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.
XXXXXXXXX
XOOOOOX X XOOXXOXXX XXXXOOOOX
X XOXXXX XX XXX X X X X
X XXXX X X X X XX
X X XXX XXXXXXXXX
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.
XXXXXXXXX
X X X X XX XXX
XXXX X
X X XXXX
XX XXXssX
X XsssX
X XXXXssX X X XssXX X XsXXX
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.
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
XXXXXXXXXXXX
This is to show X X XXX X XX the content of the X XX X X file for your X XX XX X convenience; do X X XXX X not display it like X XXXX X X that in your XX XX XX program 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 XX X X XX
X XX X X X XX XX X X X XXX X
X XXXX X X XX XX XX 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
This is to show the content of the file for your convenience; do not display it like that in your program
Sample run 3:
File: 22x40.txt
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X XXXX
X XX X
XXXXXXXXXXXXXXXXXXXXXXXXX XXXX XXXXX XXXXXXXX XXX X
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
XX XXXXX XXXXX
XXXXXXXXXXXXXXXXXXXX XXXXXXXXX
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
This is to show the content of the file for your convenience; do not display it like that in your program
Sample run 4:
File: 22x40.txt
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
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
-----
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
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 X X X X
X X
X X
X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
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: 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
XXX
X X
X X
X X
X X
X X
X X
X X
X X
XXX
-----
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
1 file (2.9MB)
