Passing through "fill" function

[Yoooooo]

Hello everyone, I've got a problem. It's about the fill function, if you ever have heard about it. This is the programm I need your help with:

  #include <iostream>
#include <fstream>
using namespace std;
int a[100][100],n,m,i,j,c=1;
void color(int i,int j)
{if(a[i][j]==1)
{a[i][j]=c;
color(i,j+1);
color(i,j-1);
color(i+1,j);
color(i-1,j);}}
int main()
{ifstream f("colors.in");
ofstream g("colors.out");
f>>n;
f>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>a[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]==1)
{c++;
color(i,j);}
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
g<<a[i][j]<<" ";
g<<endl;}
g<<"\t";
return 0;}

It actually works properly, but i can't understand how to pass through the 'color' function. At most not exactly. Here you have an example i passed through and what exactly my trouble consists of.
Example:

1 1 0 0
1 1 0 1

In the 'g' folder, it appears this:

2 2 0 0
2 2 0 3

, which is good but i can't get the way it is passed.
I tried to do it on my own but i get stuck everytime at one point:
[code]
Step 1. a[1][1]=1 =>
c=2;
step a: a[1][1]=1 => a[1][1]=2;
step b: a[1][2]=1 => a[1][2]=2;
step c: a[1][3]!=1=> get out of function and return to 'for' ?
Step 2. a[1][2]!=1;
Step 3. a[1][3]!=1;
Step 4. a[1][4]!=1;
Step 5. a[2][1]=1=>
c=3;
step a: a[2][1]=1=>a[2][1]=3;
step b: a[2][2]=1=>a[2][2]=3;
step c: a[2][3]!=1 => again, does it get out of function or something?
Step 6. a[2][2]!=1;
Step 7. a[2][3]!=1;
Step 8. a[2][4]=1=>
c=4;
step a: a[2][4]=1=>a[2][4]=4;
step b: a[2][5]!=1 bc of margins which are all 0.
And after me, the g folder would look like:
2 2 0 0
3 3 0 4

, which is not right. Where have i mistaken? What's the matter? I really can't understand.

[ne555]

your code, indented

#include <fstream>
#include <iostream>
using namespace std;
int a[100][100], n, m, i, j, c = 1;
void color(int i, int j) {
	if(a[i][j] == 1) {
		a[i][j] = c;
		color(i, j + 1);
		color(i, j - 1);
		color(i + 1, j);
		color(i - 1, j);
	}
}

int main() {
	ifstream f("colors.in");
	ofstream g("colors.out");
	f >> n;
	f >> m;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			f >> a[i][j];
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			if(a[i][j] == 1) {
				c++;
				color(i, j);
			}
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= m; j++)
			g << a[i][j] << " ";
		g << endl;
	}
	g << "\t";
	return 0;
}

> It's about the fill function, if you ever have heard about it
¿and if not? ¿why don't you bother to explain it?
Also, use the full name https://en.wikipedia.org/wiki/Floodfill

> step c: a[1][3]!=1=> get out of function and return to 'for' ?
look at the call stack

(gdb) backtrace
#0  color (i=1, j=3) at foo.cpp:6
#1  0x0000000000400b5f in color (i=1, j=2) at foo.cpp:8
#2  0x0000000000400b5f in color (i=1, j=1) at foo.cpp:8
#3  0x0000000000400d48 in main () at foo.cpp:27

it didn't find a valid cell in (1,3) so the function terminates. The execution goes up in the call stack, so back at line 8 for (1,2),
Then it executes color(i, j - 1);, that is, color(1,1), but it is already painted, so also fails.
Later it calls color(i + 1, j);, that is, color(2,2)

[Yoooooo]

Ok, I almost understood the logic of this. But there's one more thing. E.g. :

1 1 0 0 1 0 1
1 1 0 1 0 0 1
1 0 1 1 0 0 0 

I do not understand what if the function is entirely passed through, what is the cell the function restarts with. Here is what i did till now:
Step 1: a[1][1]=1 => c=2
Step a: a[1][1]=1 => a[1][1]=2
Step b: a[1][2]=1 => a[1][2]=2
Step c: a[1][3]!=1 => it returns to a[1][2], like you said
Step d: a[1][1]!=1 => still a[1][2]
Step e: a[2][2]=1 =>a[2][2]=2
Step f: a[3][2]!=1 => returns to a[2][2]
Step g: a[1][2]!=1 => returns to a[2][2]
But till now the function somehow ends, and i know it restarts, but what's that cell the function restarts with and why?

[ne555]

Run your program step-by-step through a debugger.
Look at the examples in wikipedia.

> but what's that cell the function restarts with and why?

flood_fill_1(int row, int col){
	//...
	flood_fill_2(row+1, col);
	//when the call to flood_fill_2() ends, you will be here
	//in cell (row,col) if you please
}

[Yoooooo]

I think there is one problem with my debugger, i mean with the version with my codeblocks. My version is 2.8.10 i think and debugger just tell that the process is done and some more stuff about the process of files ( whitch doesn't matter for me) . Anyway, thanks for advising, i'll try to take a look in wikipedia though.

[ne555]

¿have you set a breakpoint in color()?