Lab 3 Part 1: Flooding in the City

Deadlines

The deadline for odd-numbered groups is Tuesday 12 October 2004, 23:59:59 hours.
The deadline for even-numbered groups is Tuesday 19 October 2004, 23:59:59 hours.
Submission for even-numbered groups will not be available on Wednesday 13 October 2004 (due to the lab that is going on for odd-week).

Your file must be named cityflood.c, incorrect filename will result in zero marks. This part of the lab is worth one mark.

Overview

Recursion is a powerful problem solving tool. Although it is frequently associated with mathematical problems like factorial, power, fibonacci, pascal triangle etc, recursion can be used to solve other more interesting problem, like Tower of Hanoi etc. For this lab, we are going to use recursion to simulate flooding in a city.

Getting Started

The bird's eye view of a city (looking down from high up) can be represented by a 2D character arrays. For simplicity, we assume that a city has only two type of features:
            1. Building or Wall, represented by 'W'
            2. Street or empty space, represented by '.' (period)

An example city of 5 x 5 squares:

Now suppose that we have a REALLY heavy downpour in one of the squares in the city, water (represented by '~') will start flowing from the square, flooding the city until it reaches the edge of the city or stopped by a Wall.

The detailed "behavior" of water in the city is given below:
1. It does not flow in a square with wall.
2. It does not flow in a square already filled with water. 
3. It flows horizontally and vertically, but NOT diagonally. So, a square with water will start flowing to the top, bottom, left and right square.

So, lets see some examples (note that the examples are separated cases):

Rain in Square (0,1):

The rain water is "trapped", so all other squares are spared.

Rain in Square (2,2):

The rain water is stopped by the wall, so all other squares are spared.

Rain in Square (3,3):

The rain water flows freely, causing a huge flood in the city.

To further motivate you (or demoralize you ☺), this question is taken from a PE several years back (slightly simplified). Try and see whether you can finish this in 1 hour 45 minutes.

Bits and Pieces

Again, for generality, the city size is defined by the following constant:

#define SIZE 8

Make sure you use this constant for coding so that your program is extendable.

void PrintArray(char Message[],char Array[][SIZE]);
    Purpose:    Print the 2D Array using the following format
 

******************
Print the Message here..
******************

 012..... 7
0W.~             
1      
2
.
7   

                Note that there is NO space between the columns.          

    Input:      Array (an 2d array)
                Message (A character message)
    Output:     None. Directly display on screen. 
    Remark:     See Sample Output for the usage of the Message. 

int IsValid(int row, int column);
    Purpose:    Checks whether row and column are in the range 0 to SIZE-1
    Input:      Row (an integer representing the row number)
                Column (an integer representing the column number)
    Output:     1 (True. The row and column are well defined)
                0 (False. Either the row or column is out of range)
    Remark:     You can choose NOT to implement or use this function.

void WaterAt(char City[][SIZE], int row, int column);
    Purpose:    A recursive function to simulate the flooding.
    Input:      City (the 2d array that represents the city)
                Row (an integer representing the row number)
                Column (an integer representing the column number) 
    Output:     None. See remark.
    Remark:     The array City is directly manipulated. 

Putting it together

With the help of the functions above, you can now design the main function. The basic steps is given as follows:

    Basic Steps:

        1. Print the city.
        2. Ask for coordinate to rain.
        3. If coordinate is valid, flood the city accordingly and go to step 1.
        4. If coordinate is invalid, end the program.

Skeleton Code

Note that the city 2d array is Already initialized for you. Also, a useful function, Reading( ) is provided.

#include <stdio.h>

#define SIZE 8

int Reading(char[]);
int isValid(int, int);
void PrintArray(char[],char[][SIZE]);
void WaterAt(char[][SIZE],int,int);

int main()
{
    //The City is already intialized for you
    char city[SIZE][SIZE] = { {'.','.','.','W','.','.','.','.'},
                              {'W','.','W','W','W','.','W','.'},
                              {'W','.','W','.','W','W','.','W'},
                              {'W','.','.','.','W','.','W','.'},
                              {'W','W','W','W','W','.','.','W'},
                              {'.','W','.','.','W','.','.','.'},
                              {'.','W','W','W','W','.','W','.'},
                              {'W','.','.','W','.','.','W','.'}
                            };
}

int Reading(char msg[])
{
    int input;

    printf(msg);
    scanf("%d",&input);

    return input;
}

int isValid(int X, int Y)
{
}

void PrintArray(char Msg[],char City[][SIZE])
{
}

void WaterAt(char City[][SIZE],int Row, int Column)
{
}

Sample Output

Note: User Input is in bold.

******************
The City
******************

 01234567
0...W....
1W.WWW.W.
2W.W.WW.W
3W...W.W.
4WWWWW..W
5.W..W...
6.WWWW.W.
7W..W..W.

Row: 2
Column: 1

******************
The City
******************

 01234567
0~~~W....
1W~WWW.W.
2W~W~WW.W
3W~~~W.W.
4WWWWW..W
5.W..W...
6.WWWW.W.
7W..W..W.
Row: 2
Column: 6
******************
The City
******************

 01234567
0~~~W....
1W~WWW.W.
2W~W~WW~W
3W~~~W.W.
4WWWWW..W
5.W..W...
6.WWWW.W.
7W..W..W.

Row: 3
Column: 0

******************
The City
******************

 01234567
0~~~W....
1W~WWW.W.
2W~W~WW~W
3W~~~W.W.
4WWWWW..W
5.W..W...
6.WWWW.W.
7W..W..W.

Row: 8
Column: 8

Program Terminated. Bye Bye!