fill until boundary

samTheProgrammer (4)
Hello! This is an assignment and I'm not necessarily looking for a solution (but feel free to lol! I'm not plagiarizing in any means). More about how-to as I'm not sure how to proceed with the certain problem.

This is basically a 2D array implementation of a paint bucket tool's fill option. Suppose I have a closed boundary where 0 represents white and 1 represents red like so:
This is a 2D array with row = 11 and col = 6

1
2
3
4
5
6
7
8
9
 
|X|0 1 2 3 4 5 6 7 8 9 10 |
+---------------------------+
|0|0 0 0 0 0 0 0 1 1 1 1   |
|1|0 0 0 0 0 0 1 0 0 0 1   |
|2|0 0 0 0 0 0 1 0 0 0 1   |
|3|0 0 0 0 1 1 0 0 0 0 1   |
|4|0 0 0 0 0 1 0 0 0 0 1   |
|5|0 0 0 0 0 0 1 1 1 1 1   |
+---------------------------+



after calling fill(8,2), it should fill in the region bounded by 1's i.e red.

1
2
3
4
5
6
7
8
9
 
|X|0 1 2 3 4 5 6 7 8 9 10 |
+--------------------------+
|0|0 0 0 0 0 0 0 1 1 1 1  |
|1|0 0 0 0 0 0 1 1 1 1 1  |
|2|0 0 0 0 0 0 1 1 1 1 1  |
|3|0 0 0 0 1 1 1 1 1 1 1  |
|4|0 0 0 0 0 1 1 1 1 1 1  |
|5|0 0 0 0 0 0 1 1 1 1 1  |
+---------------------------+


How am I supposed to go about this recursively? or by using an STL stack?

The problem statement is the following:

Construct a class that makes an nxm grid passed as args in the constructor, reads from an open input stream n by m values and stored in the grid by overloading the >> operator. Has 4 versions of fill where one is recursive, one uses STL stack (efficient), one uses STL stack (non-efficient), one uses Queue and outputs to an open output stream using overloaded << operator. Implement those and copy constructor and destructor.

Now I know the following: for the Queue problem I'm probably going to have to enqueue the starting point, store the neighbours, check for the red pixel and continue and for recursive one, probably a little bit of backtracking.

Any feedback will be appreciated.
Last edited on
JLBorges (13770)
mbozzi (3932)
If you prefer an example in C++, @tpb's made a great post here:
http://www.cplusplus.com/forum/general/243382/#msg1081359
samTheProgrammer (4)
@mbozzi Thank you! I'll try to play around with it a little bit to see what I can do
samTheProgrammer (4)
I don't think the flood algorithm that @tpb posted is exactly what I'm looking for, it doesn't exactly give me much insight as I'm quite new to C++ :(
lastchance (6980)
Procedural version. Your assignment asks for an object-oriented version and proper input.

Please note that the array is 0-indexed and (i,j)=(down,across), so here it starts from (2,8).

For a recursive version replace the pushing onto the stack by a recursive call. That's all.

These are the "non-efficient" versions. If you want more efficient versions scan all the way along each direction until you hit a 1 or the edge of the grid; the current versions only consider nearest neighbours.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <utility>
using namespace std;

using matrix = vector< vector<int> >;


//======================================================================


void floodfill_stack( matrix &grid, int i, int j )
{
   int rows = grid.size();
   int cols = grid[0].size();
   if ( i < 0 || i >= rows || j < 0 || j >= cols ) return;
   if ( grid[i][j] ) return;

   stack< pair<int,int> > stk;
   stk.push( { i, j } );
   while ( !stk.empty() )
   {
      auto p = stk.top();   stk.pop();
      i = p.first;   j = p.second;
      grid[i][j] = 1;
      if ( i > 0        && !grid[i-1][j] ) stk.push( { i - 1, j } );
      if ( i < rows - 1 && !grid[i+1][j] ) stk.push( { i + 1, j } );
      if ( j > 0        && !grid[i][j-1] ) stk.push( { i, j - 1 } );
      if ( j < cols - 1 && !grid[i][j+1] ) stk.push( { i, j + 1 } );
   }
}


//======================================================================


void floodfill_recursion( matrix &grid, int i, int j )
{
   int rows = grid.size();
   int cols = grid[0].size();
   if ( i < 0 || i >= rows || j < 0 || j >= cols ) return;
   if ( grid[i][j] ) return;

   grid[i][j] = 1;
   floodfill_recursion( grid, i - 1, j );
   floodfill_recursion( grid, i + 1, j );
   floodfill_recursion( grid, i, j - 1 );
   floodfill_recursion( grid, i, j + 1 );
}


//======================================================================


void display( string title, const matrix &grid )
{
   cout << title << '\n';
   for ( auto row : grid )
   {
      for ( auto e : row ) cout << e;
      cout << '\n';
   }
}


//======================================================================


int main()
{
   matrix grid = {
                   { 0,0,0,0,0,0,0,1,1,1,1 },
                   { 0,0,0,0,0,0,1,0,0,0,1 },
                   { 0,0,0,0,0,0,1,0,0,0,1 },
                   { 0,0,0,0,1,1,0,0,0,0,1 },
                   { 0,0,0,0,0,1,0,0,0,0,1 },
                   { 0,0,0,0,0,0,1,1,1,1,1 }
                 };

   display( "\nInitial:", grid );
   floodfill_stack( grid, 2, 8 );
// floodfill_recursion( grid, 2, 8 );
   display( "\nFilled:", grid );
}


//====================================================================== 



Initial:
00000001111
00000010001
00000010001
00001100001
00000100001
00000011111

Filled:
00000001111
00000011111
00000011111
00001111111
00000111111
00000011111
Last edited on
samTheProgrammer (4)
@lastchance, thank you so much! I worked on mine last night and built upon the flood fill algorithm that @mbozzi referenced, however, I'll play with yours to find out how I can make mine better, thank you so much for the help! <3
Topic archived. No new replies allowed.