Texas Real Estate Study: Project # 4

A construction company owns a large piece of real estate within the state of Texas. Recently, the company decided to develop this property. Upon inspection of the property, however, it was revealed that the land, at various locations, contained bodies of water. This came as a shock to the owners of the company, for they were from out of state and not familiar with wetlands of East Texas. The situation was very grave and the owners not knowing that such bodies of water can be converted to beautiful lakes that will increase the value of the land around them, were about to abandon the construction project. Fortunately, this fact was brought to the owners’ attention by a smart MSU graduate who worked for the company and consequently the construction project started. The engineers divided the construction site by a grid into uniform square cells such that each square cell entirely contained either water or land. (How they did it, of course, is anybody’s guess.) Now, the question that the engineers are to answer is the following: “Given the row and column number of a grid cell that contains water, what is the area of the lake containing that cell.” (an area is measured by number of grid cells it contains. Diagonal cells are considered to be adjacent.) You are to write a program to answer this question!

Input: The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a three positive integers R,C and Q which represent the number of rows, the number of columns and the number of query pairs. The input consists of 1 < R≤ 99 lines each containing 1 < C ≤ 99 character long sequence of ‘L’s and ‘W’s followed by Q > 0 lines each containing a pair of integers i and j. The first R lines will represent the R×C grid covering the land where a ‘W’/‘L’ at the c-th character of the r-th line indicates water/land within the cell at row r and column c of the grid. The pairs of integers on the last Q lines, each represent the row and column numbers of some grid cell that contains water.

Output: For each test case, the output must follow the description below . The outputs of two consecutive cases will be separated by a blank line. First print the grid.  The output for each pair of integers, i and j, on the last Q lines of input, consists of an integer, on a separate line, indicating the area of the lake containing the grid cell, at row i and column j of the grid. This is followed by “: start=” and then the starting cell in parens. See format below. All indexing here starts at 1 not 0.  Remember, there will be multiple test cases in the data set. Here are two to practice with.

 2
 9 9 2
 LLLLLLLLL
 LLWWLLWLL
 LWWLLLLLL
 LWWWLWWLL
 LLLWWWLLL
 LLLLLLLLL
 LLLWWLLWL
 LLWLWLLLL
 LLLLLLLLL
 3 2
 7 5
 4 20 4
 LLWLLLLLLLLLLLLLWLLL
 WLLLLLLLWLLLLWWLWLLL
 LLWWLLLLWWLWLWLLLLWL
 LWWLLLWWLWLLLLLWLLLL
 4 2
 2 1
 1 3
 2 9

Sample Output for the first case.

 LLLLLLLLL
 LLWWLLWLL
 LWWLLLLLL
 LWWWLWWLL
 LLLWWWLLL
 LLLLLLLLL
 LLLWWLLWL
 LLWLWLLLL
 LLLLLLLLL

12: start=(3,2)
4: start=(7,5)

In order to work on this problem you are to create a project in Visual Studio and add a data file called data.txt to the problems directory which contains the test data above. In order to read this data file you are to redirect this file into cin by adding the extension <data.txt to the Visual Studio command line parameter.  Go to Project|pname properties|debugging and set Command Arguments to <data.txt 

When you write the above program all you need to do is read from cin.  With the above setup it will automatically read from data.txt without you having to open files etc.  This is just the method used when submitting programs to the UVa Online Judge.

TO TURN IN.

Turn in a well documented project printout together with you project on a jump drive. Put the entire visual studio project on the drive so I can compile and run it.  I will feed different data to your program to test it.  Put this in an envelope with your name on the front and project 4 on the outside.

EXAMPLE 1D example solution that I discussed in class

// 9: Counting the size of a contiguous grouping’s of b’s in a char array
// ie str=” bbb bbbbbbb bb b bbbbb bbb ”
// I have put a blank at the front and end to simplify the problem
// Here is some calls.
//char s[] = ” b b bbb b bbbbbb bbb “;

//cout << bCount(s,6) << endl;
//char t[] = ” b b bbb b bbbbbbbbbbbbbb bbb “;
//cout << bCount(t,13 ) << endl;

int bCount(char s[], int pos) {
 if (s[pos] == 'b') {
      s[pos] = '.';//remove the 'b'
      return(1+bCount(s,pos + 1)+bCount(s,pos-1));// Note how the blank on each end                                                                                                      // simplifies this.
 }
 else
    return 0;
 return 0;
 }

Comments are closed.