Need help getting started....

[hwlibra083]

I'm a little confused on how to even start this problem. Here's the problem:

Given a square matrix, write a program that determines the number of white blocks and total number of squares in each of the white blocks. By definition the outside boundaries of the matrix must be shaded. A block of white squares consists of all of the white squares whose side boundaries are adjacent to another white square. White squares that touch only at a diagonal point are not adjacent.

Obtain the square definition from a text file. The file should contain a square matrix composed of zeros for shaded squares and nonzero values for white squares. The matrix should be allocated from dynamic memory.

At the end of the program, print a report showing the number of white blocks and the number of squares in each.

Here's the matrix:

0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 2 2 2 2 0
0 1 1 0 0 2 2 2 2 0
0 0 0 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4 0 0
0 0 0 0 4 4 4 0 0 0
0 0 0 0 0 4 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

We are supposed to implement the use of stacks in this program. I'm just confused on how to use them with this problem. My first inclination is to read the matrix into a multi-dimensional array, but where do the stacks come in? We are using C, so if anyone can explain this to me a little better than the stupid book is explaining stacks and this problem to me, I would be forever indebted to them for the rest of my life! :o)

Thanks!

[abhimanipal]

Do you have sample input and out put ? Can you post that ?

[hwlibra083]

Do you have sample input and out put ? Can you post that ?

The input is the matrix from a .txt file (the matrix already posted) output is the number of white blocks (those numbered in the matrix), basically the total of all of the numbered blocks, and how many are in each. For example: they are numbered - 1, 2, 3, 4 (4 blocks) and there are 3 squares in block 1, 8 squares in block 2, 1 square in block 3, and block 4 has 9 squares.

[hwlibra083]

Can anyone help me?

[abhimanipal]

I am sorry I cannot understand the problem.....
In one of your earlier posts you had pasted the matrix. For that matrix what is the output ?

[hwlibra083]

It would be something like this:

Number of blocks: 4

Number of squares in block 1: 3
Number of squares in block 2: 8
Number of squares in block 3: 1
Number of squares in block 4: 9

Thanks for trying to understand. I appreciate it.

[abhimanipal]

Ok.... I think I have finally understood the question..
You could try to do some thing of this sort..

For each row
For each column
When you see a non zero number say a, check its 4 sides and push the positions of all the non zero numbers in a stack. Then pop the first element say b and push the positions of all of its non zero neighbors onto the same stack. Not the stack contains the positions of non zero neighbors of the both a and b. If you go on this way, by the time, the stack is empty you would have finished the first square

[hwlibra083]

How would I check it's 4 sides?

[abhimanipal]

current row + 1, current row -1, current col +1, current col -1
But you will have to take care of the boundary conditions

[emsh]

Hey are you in the data structures class in tucson? Wondering if you could help me?

[hwlibra083]

Hey are you in the data structures class in tucson? Wondering if you could help me?

Bower's class? Yeah, I would love to help you, but I'm still stuck. What do you have so far? I'm as far as reading in the file.

[emsh]

Bower's class? Yeah, I would love to help you, but I'm still stuck. What do you have so far? I'm as far as reading in the file.

Well thats more then I had and still. I met with him tonight.. idk but I feel as if I have not learned enough from all of these classes. He told me that I know what to do logically and just need to figure out how to implement the code. So if I can get anything together I might be bouncing so stuff off of you. If you don't mind.

[zeesa]

how i creat software

[hwlibra083]

Well thats more then I had and still. I met with him tonight.. idk but I feel as if I have not learned enough from all of these classes. He told me that I know what to do logically and just need to figure out how to implement the code. So if I can get anything together I might be bouncing so stuff off of you. If you don't mind.

That's sounds good, I'll pretty much be working on it all day. I'll post what I have so far. If you have any ideas, let me know.

Purpose:             Given a square matrix, this program determines the number of white blocks
                        and total number of squares in each of the white blocks.  The square 
                        is read in from a text file, and a printed report is printed showing
                        the number of white blocks and the number of squares in each.
*/

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#define  MAXLINELEN 18

FILE  *getOpen();         // Function Prototype

int main()
{  
   
   FILE        *inFile;  // Declares inFile pointer as a FILE type.
   STACK       *stack;   // Declares stack pointer as a STACK type.
   int         **matrix; // Declares matrix pointer as a int type.
   int          nrows;   // number of rows.
   int          ncolumns;// number of columns.
   int          i;
   char         singleLine[MAXLINELEN];
   
   // Open the text file containing the matrix.
   inFile = getOpen();
   
   // Read in each line of the matrix from the .txt file.
   nrows = 0;
   
   while (fgets(singleLine, MAXLINELEN - 1, inFile) != NULL)
   {
         nrows++;
         printf("#%d: %s\n", nrows, singleLine);
   }
   
   // Dynamically allocate memory for the read in matrix.
   matrix = malloc(nrows * sizeof(int *));
   if(matrix == NULL)
   {
        printf("Out of memory.\n");
        exit(1);
   }
   for(i = 0; i < nrows; i++)
   {
        matrix[i] = malloc(ncolumns * sizeof(int *));
        if(matrix[i] == NULL)
        {
             printf("Out of memory.\n");
             exit(1);
        }
   }
   printf("Memory allocated successfully!\n");
   
   
   
   
   system("pause");
   return 0;
   
}
   
/* =============================================
                   getOpen
   =============================================
   This function opens the file for reading, and 
   returns the file name back to the program for 
   use.
*/
FILE *getOpen()
{
     FILE *fname;
     char name[21];
     
     printf("\nEnter a file name: ");
     gets(name);
     fname = fopen(name, "r");
     if (fname == NULL)
     {
          printf("Failed to open the file %s.\n", name);
          exit(1);
     }
     printf("File was successfully opened!\n");
     
     return(fname);
}

I don't want to say your name on here. Is this the "other girl in the class"? Cuz I'm one of two. HE HE!

[emsh]

Yeah! I figured. I'm guessing we both write like girls, because I thought it was you. I got an extension. If you need one he'll most likely give it to you.

[emsh]

After the first line in the file is read, checked for all zeros and counted. The matrix should be two less. Meaning if there are 10 enteries then the matrix would be an 8x8, as not to use unnecessary memory. Not only that it also needs a cell flag, a recursive call to let one know where they have been when maneuvering through the matrix.

[hwlibra083]

After the first line in the file is read, checked for all zeros and counted. The matrix should be two less. Meaning if there are 10 enteries then the matrix would be an 8x8, as not to use unnecessary memory. Not only that it also needs a cell flag, a recursive call to let one know where they have been when maneuvering through the matrix.

That makes sense! That's pretty much the way that me and this other guy in our class have been playing with. I'll post the idea he's had too:

Able to solve the problem of how to not count the same blocks/boxes repeatedly. After you push the pointers onto the stack as you find the adjacent white boxes, you pop them off and count them, then here's the key: you change their value to a 0. Then they become shaded boxes and your program won't count them again. Then you just have it loop until there are no more white boxes and the program is done. Another trick is that you need to use two counters. One counter gets printed each run of the loop to indicate the number of white boxes in a block, then the last counter is printed to indicate how many total blocks were found.

This is good, putting heads together!

[hwlibra083]

I'm still having a lot of trouble coding this problem. Is anyone out there who can help me? The recent code postings is still how far I am, which is not far at all. Where do go I go from where I am at?

ANY help, would be greatly appreciated.

Thanks