help me with program logic

[miloserdniy5]

From a rectangular sheet of paper tartan (N rows, M columns) have removed some of the cells. How many pieces fall apart the rest of the sheet? Two cells do not break if they have a common side.
help me with base idea

[Handy Andy]

Hello miloserdniy5,

is this the correct full instructions?

The first problem I see is:

Two cells do not break if they have a common side.

Thinking about it each corner has two common sides and those in the middle, of the outer edge, have 3 common sides, so the way I take it is that nothing will fall off.

If this is a school assignment then post the instructions that you were given so everyone knows what you are trying to do. If this is from a book then the name of the book and page number would be helpful/

Andy

[dutch]

@Andy,

Example of 5 rows by 8 columns with 6 cells removed.
I assume the O pieces will "fall apart".

X X X X X X   O
X X   X X X X
X   O   X X X X
X X   X X X X X
X X X X X X X X

@miloserdniy5

Is that correct?
How large can N and M be?

[miloserdniy5]

that's all instruction i have.

[lastchance]

Connect a graph - e.g. by using an array and a stack.

However, you are going to have to declare some point that is definitely in "the rest of the sheet". In principle, you could take @dutch's example and say that one of the O's was the rest of the sheet and everything else fell away from it.

You must have some more information than that, @miloserdniy5. Please quote it verbatim, not what you think it says.

[Handy Andy]

@dutch,

Not being there from the beginning I was looking at it from a different angle. Also lack of information did not help.

That makes more sense now.

Andy

[dhayden]

I think the question is asking how many pieces make up the remaining paper. So it Dutch's example, the answer is 3: one piece of X's, and two O pieces.

You solve this recursively. Given a square in a remaining sheet, recursively find all the connected squares. Together they make up one piece. Then go through the squares until you find another remaining sheet and call the recursive function again.

[dhayden]

I had some time to do this one. Here it is, with the important bits left for you to do.

#include <vector>
#include <iostream>

using std::cin;
using std::cout;
using std::vector;
using std::endl;

// I represent a matrix as a vector of vectors. Each square is one
// character. "X" means it's an unmarked piece of the original sheet.
// ' ' means it's a square that was removed.  Anything else means
// it's part of a connected piece.
typedef vector<vector<char>> Board;

// Starting at row and column, recursively mark all connected,
// unmarked squares with the character ch.  Be sure that row and col
// don't become invalid.  In the call, I use different characters for
// different pieces.
void
markSheet(Board &b, int row, int col, char ch)
{
    // YOU MUST WRITE THIS CODE
}

// Read the board and cut out squares from cin. The format is
// N M
// s
// row col
// row col
// ...
// row col

// N and M are the number of rows and columns in the original sheet
// s is the number of squares that are removed.
// each row & col is the row and column of a square that is removed.
void
readBoard(Board &b)
{
    // YOU MUST WRITE THIS CODE
}
	
// Print the board to cout
void printBoard(Board &b)
{
    // YOU MUST WRITE THIS CODE
}

int main()
{
    Board b;
    readBoard(b);
    char mark = 'A';
    for (unsigned i=0; i< b.size(); ++i) {
	for (unsigned j=0; j<b[i].size(); ++j) {
	    if (b[i][j] == 'X') {
		markSheet(b, i, j, mark);
		++mark;
	    }
	}
    }
    printBoard(b);
    cout << "There are " << mark-'A' << " sheets left\n";
}

Input:

5 8
6
1 7
2 3
2 8
3 2
3 4
4 3

Output:

Original sheet:
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

Separated Sheet
A A A A A A   B
A A   A A A A
A   C   A A A A
A A   A A A A A
A A A A A A A A
There are 3 sheets left

[dutch]

Cool. Here's another input:

5 10
23
0 1  0 2  0 3  0 7  0 8
1 3  1 7  1 9
2 1  2 2  2 3  2 6  2 7  2 9
3 1  3 3  3 4  3 5
4 2  4 4  4 6  4 8  4 9

Original Sheet
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    

Separated Sheet
A       B B B     C
A A A   B B B   D  
A       B B     D  
A   E       D D D D
A A   F   G   D    

There are 7 separate sheets.

[dhayden]

I get the same output as dutch for his new example.

One important note though: his input gives the actual C++ indexes of the squares to cut away (i.e, the left corner is 0,0). The input in my example uses human-friendly indexes that start at 1. So if you want to try the two cases, you'll have to modify one of the inputs.

[dutch]

Just wrote it up myself, like a floodfill. Here's another example, in a different format but still easy to read since cin >> ch skips space. I hadn't notice your 1-based indices, which is quite common with input.

10 20
. . . . . . 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 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

[dhayden]

I like that input format. For the OP, here is the result I get:

. . . . . . A A A A A A A A A A . . . .
B B B B B . A A . . . . . A A A A A . C
B B B B B . A A . . . . . A . A A A . C
B . . . . . A A . D D D . A . A A A . C
B . . . . . . . . D D D D . . A A A . .
B B B B . . . . . D . . . . . . . . E E
B B B B . . . . D D D D D D . . . . E E
B . . B B . . F . . . D . D . . . . E E
. . . B B . F F F . . D . D . . . . E E
. . B B . F F F F . . D D . E E E E E E
There are 6 sheets left