Groovy hepcat Simon Biber was jivin' on Wed, 3 Dec 2003 14:52:59 +1100
in comp.lang.c.
Re: Task Problem!!!!'s a cool scene! Dig it!
Ivo said:
Could someone please solve the following problem:
There is a given txt file like this (example):
00011100001000
00100011110100
00100000000010
00010000000001
00010000000010
00001000000100
00000111111000
We should read the txt file and...
The 1's make an outline (shape) - contour. This info should be placed
in
a matrix [rxc] elements. The Task is to fill this shape (to color) the
contour with 1's - inside. Such colored matrix should be printed.
you want something that detects the border of ones and does not change
them? Hint -- investigate recursive algorithms.
Nonsense. This is an iterative problem, not a recursive one.
Here's some untested code to give you the gist:
void fill(int area[C][R], int x, int y, int fromcolour, int tocolour)
{
if(area[x][y] == fromcolour)
{
area[x][y] = tocolour;
fill(area, x + 1, y, fromcolour, tocolour);
fill(area, x - 1, y, fromcolour, tocolour);
fill(area, x, y + 1, fromcolour, tocolour);
fill(area, x, y - 1, fromcolour, tocolour);
}
}
I suggest you test it. You may experience a stack overflow problem
(on stack based implementations), especially with a large region to be
filled. This recursive solution is very bad. A better way of doing
what you suggest is iterative, or at least a mix of iteration and
recursion, like the following:
#include <stdio.h>
static void xfill(unsigned char *rgn, size_t w, size_t h, size_t x,
size_t y, int clr, int bg_clr)
{
long start, end;
/* don't go off edge of region */
if(x >= w || y >= h)
return;
/* don't go over different colour */
if(rgn[y * w + x] != bg_clr)
return;
for(end = x; end < w && rgn[y * w + end] == bg_clr; end++)
rgn[y * w + end] = clr;
for(start = x - 1; start >= 0 && rgn[y * w + start] == bg_clr;
start--)
rgn[y * w + start] = clr;
/* recurse for < y */
if(y > 0)
for(start++, x = start; start < end; start++)
xfill(rgn, w, h, start, y - 1, clr, bg_clr);
/* recurse for > y */
if(y < h - 1)
for(start = x; start < end; start++)
xfill(rgn, w, h, start, y + 1, clr, bg_clr);
}
void fill(unsigned char *rgn, size_t w, size_t h, size_t x, size_t y,
int clr)
{
unsigned char bg_clr = rgn[y * w + x];
/* don't bother to fill same colour */
if(clr != bg_clr)
xfill(rgn, w, h, x, y, clr, bg_clr);
}
#define MAP_WIDTH 15
#define MAP_HEIGHT (sizeof map / sizeof *map)
#define X_Fill_COORD 3
#define Y_FILL_COORD 1
#define FILL_CHAR '2'
int main(void)
{
char map[][MAP_WIDTH] =
{
"00011100001000",
"00100011110100",
"00100000000010",
"00010000000001",
"00010000000010",
"00001000000100",
"00000111111000"
};
int i;
puts("Before the fill:");
for(i = 0; i < MAP_HEIGHT; i++)
{
puts(map
);
}
fill((char *)map, MAP_WIDTH, MAP_HEIGHT, X_Fill_COORD, Y_FILL_COORD,
FILL_CHAR);
puts("\nAfter the fill:");
for(i = 0; i < MAP_HEIGHT; i++)
{
puts(map);
}
return 0;
}
However, that may be overkill for the OP's purposes. As TroLoo
suggested, all he has to do is scan each line until he finds the
outline, then store the fill character until he again encounters the
outline, then continue scanning the rest of the line. This is a
completely iterative solution to the problem, and wouldn't require the
OP to first find a set of coordinates inside the outline (as the
solutions you and I posted do).
--
Dig the even newer still, yet more improved, sig!
http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?