SUBJECT: DATA STRUCTURES [CSE 2103] Assignment 3 Instructions: Refer to the Codi
ID: 3871545 • Letter: S
Question
SUBJECT: DATA STRUCTURES [CSE 2103] Assignment 3 Instructions: Refer to the Coding Standards attached with this Question Paper Avoiding Plagiarism while writing the code. Submission guidelines will be circulated shortly (xy-1) 8-neighbourhood Maze problem: A binary matrix is given say B, the task is to find sequence of moves from a given initial location (Xn, Yo) in the matrix, to a final location (Xo. Y) explicitly using stack. [ (0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0,0, Ex: Intial Location (Xn, Yo) = (0, 2) 0,0,1, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 1,1, 0, 0, 0,0, 0,0,1, 0, 0, 0,0, 0, 0, 0, 0, 0,0, 0, 0, 1, 0, 0, 0,0, 0,0,1, 0, 0, 0,0, 0, 0, 0, 0, 0,0,0, 0,1,1, 0, 0,0), t0, 0, 1, 0, 0,0,0, 0, 0,0, 0, 0,0, 0, 0, 0, 1, 0,0,0 t0,0, 1, 0, 0,0,0, 0, 0,0, 0, 0,0, 0, 0, 0, 1, 0,0,0) 0 0 0 0 0 01 0 0 0 0 0 010 Final Location (X %)=(7,4) 1. t0,0, 0, 0, 0,0,0,1 0,0, 0, 0,0,0, 0, 1, 0, 0,0,0 t0,0, 0, 0, 0,0,0,1, 0,0, 0, 0,0,0, 0, 1, 0, 0,0,01 0,0, 0, 0, 0,0,0,1,1,1,0, 0,0,0, 0, 1, 0, 0,0,01 0 0 1 01 The initial position Xa, Yo has 1 as the element. A move can be made to a location; only if there is 1 in the neighboring co-ordinate (only 4- neighbors are considered ignoring diagonal neighbors). In the above example from initial location (0,2) the possible move is (1,2). From (1, 2) the possible moves are (0,2), (13), (1,1) and (2,2). So the expected output for the input (0,2) as start and (7,4) 0,0, 0, 0, 0,0,0, 0, 0,0, 0,0,0,0, 0, 0, 0, 0,0,01 Expected result on selectin (6,10) as a seed point is given as as the destination is, a sequence 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,0 There can be similar other paths. an array similar to the one g iven below, we can see that the Flood fiil without recursion: Consider 1's in the matrix is forming a elosed contour. In a flood fill operation the user gives a point as the seed point, for example any location (x, y) say (6, 10), can be the seed point. The flood fill algorithm mll the entire region inside the closed contour of 1's. However if 1's are not forming 2. a closed contour the entire matrix becomes 1's (called as leakage). If the seed point is chosen outside the contour of 1's, then outer region of the contour must be filled with 1's. (either 4- Neighbourhood or 8-Neighbourhood elements can be considered) ample of four neighborhood and eight nei 0,0, 0, 0, 0,0,0, 0, 0,0, 0,0,0, 0, 0, 0, 0, 0,0,0Explanation / Answer
Input:
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
x = 4, y = 4, newColor = 3
The values in the given 2D screen indicate colors of the pixels.
x and y are coordinates of the brush, newColor is the color that
should replace the previous color on screen[x][y] and all surrounding
pixels with same color.
Output:
Screen should be changed to following.
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 3, 3, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 3, 3, 0},
{1, 1, 1, 1, 1, 3, 1, 1},
{1, 1, 1, 1, 1, 3, 3, 1},
};
floodFil(screen[M][N], x, y, prevC, newC)
1) If x or y is outside the screen, then return.
2) If color of screen[x][y] is not same as prevC, then return
3) Recur for north, south, east and west.
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);
void floodFillUtil(int screen[][N], int x, int y, int prevC, int newC)
{
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != prevC)
return;
// Replace the color at (x, y)
screen[x][y] = newC;
// Recur for north, east, south and west
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);
}
void floodFill(int screen[][N], int x, int y, int newC)
{
int prevC = screen[x][y];
floodFillUtil(screen, x, y, prevC, newC);
}
// Driver program to test above function
int main()
{
int screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
int x = 4, y = 4, newC = 3;
floodFill(screen, x, y, newC);
cout << "Updated screen after call to floodFill: n";
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
}
extern int nMinX, nMaxX, nMinY, nMaxY;
void LineFill_3(int x1, int x2, int y,
COLORREF fill_color, COLORREF seed_color)
{
int xL,xR;
if( y < nMinY || nMaxY < y )
return;
for( xL = x1; xL >= nMinX; --xL ) { // scan left
if( GetPixel(xL,y) != seed_color )
break;
SetPixel(xL,y,fill_color);
}
if( xL < x1 ) {
LineFill_3(xL, x1, y-1, fill_color, seed_color); // fill child
LineFill_3(xL, x1, y+1, fill_color, seed_color); // fill child
++x1;
}
for( xR = x2; xR <= nMaxX; ++xR ) { // scan right
if( GetPixel(xR,y) != seed_color )
break;
SetPixel(xR,y,fill_color);
}
if( xR > x2 ) {
LineFill_3(x2, xR, y-1, fill_color, seed_color); // fill child
LineFill_3(x2, xR, y+1, fill_color, seed_color); // fill child
--x2;
}
for( xR = x1; xR <= x2 && xR <= nMaxX; ++xR ) { // scan betweens
if( GetPixel(xR,y) == seed_color )
SetPixel(xR,y,fill_color);
else {
if( x1 < xR ) {
// fill child
LineFill_3(x1, xR-1, y-1, fill_color, seed_color);
// fill child
LineFill_3(x1, xR-1, y+1, fill_color, seed_color);
x1 = xR;
}
// Note: This function still works if this step is removed.
for( ; xR <= x2 && xR <= nMaxX; ++xR) { // skip over border
if( GetPixel(xR,y) == seed_color ) {
x1 = xR--;
break;
}
}
}
}
}
void SeedFill_3(int x, int y, COLORREF fill_color)
{
COLORREF seed_color = GetPixel(x,y);
if( fill_color != seed_color )
LineFill_3(x,x,y,fill_color,seed_color);
}
extern int nMinX, nMaxX, nMinY, nMaxY;
typedef struct { int x1, x2, y, dy; } LINESEGMENT;
#define MAXDEPTH 10000
#define PUSH(XL, XR, Y, DY)
if( sp < stack+MAXDEPTH && Y+(DY) >= nMinX && Y+(DY) <= nMaxY )
{ sp->xl = XL; sp->xr = XR; sp->y = Y; sp->dy = DY; ++sp; }
#define POP(XL, XR, Y, DY)
{ --sp; XL = sp->xl; XR = sp->xr; Y = sp->y+(DY = sp->dy); }
// Fill background with given color
void SeedFill_4(int x, int y, COLORREF new_color)
{
int left, x1, x2, dy;
COLORREF old_color;
LINESEGMENT stack[MAXDEPTH], *sp = stack;
old_color = GetPixel(x, y);
if( old_color == new_color )
return;
if( x < nMinX || x > nMaxX || y < nMinX || y > nMaxY )
return;
PUSH(x, x, y, 1); /* needed in some cases */
PUSH(x, x, y+1, -1); /* seed segment (popped 1st) */
while( sp > stack ) {
POP(x1, x2, y, dy);
for( x = x1; x >= nMinX && GetPixel(x, y) == old_color; --x )
SetPixel(x, y, new_color);
if( x >= x1 )
goto SKIP;
left = x+1;
if( left < x1 )
PUSH(y, left, x1-1, -dy); /* leak on left? */
x = x1+1;
do {
for( ; x<=nMaxX && GetPixel(x, y) == old_color; ++x )
SetPixel(x, y, new_color);
PUSH(left, x-1, y, dy);
if( x > x2+1 )
PUSH(x2+1, x-1, y, -dy); /* leak on right? */
SKIP: for( ++x; x <= x2 && GetPixel(x, y) != old_color; ++x ) {;}
left = x;
} while( x<=x2 );
}
}
int CQuickFill::QuickFill(
CBitmap* pBitmap,int x,int y,
COLORREF fill_color,COLORREF border_color/*=CLR_INVALID*/)
{
COLORREF ThisColor;
int MaxY,MaxX,dy;
int ChildLeft,ChildRight;
int ParentLeft,ParentRight;
#ifdef QUICKFILL_SLOW
HWND hWnd;
if( m_bSlowMode )
hWnd = ::GetActiveWindow();
#endif
if( !m_DibData.CreateDIB(pBitmap) )
return -3;
#ifdef QUICKFILL_TEST
SHORT nKeyState;
m_CurStackSize = m_MaxStackSize = m_VisitSize = 0U;
m_CurrentLine = 0;
#endif
m_bXSortOn = m_bMemError = FALSE;
m_LastY = -1;
if( CLR_INVALID != border_color ) {
ThisColor = GetPixel(x,y);
if( ThisColor == border_color )
return -1;
ThisColor = border_color;
m_bXSortOn = TRUE;
}
else {
ThisColor = GetPixel(x,y);
if( ThisColor == fill_color && !m_DibPattern.GetDibPtr() )
return -1;
if( m_DibPattern.GetDibPtr() || memcmp(m_FillMask,_SolidMask,8) )
m_bXSortOn = TRUE;
}
/* Using macros because we can not uses pointer to member functions.
* This makes the code less efficient, but solves the problem.
*/
#define FindLeft(x,y,xmin,color)
((CLR_INVALID != border_color)
? SearchLeft(x,y,xmin,color) : ScanLeft(x,y,xmin,color))
#define FindRight(x,y,xmax,color)
((CLR_INVALID != border_color)
? SearchRight(x,y,xmax,color) : ScanRight(x,y,xmax,color))
#define SkipRight(x,y,xmax,color)
((CLR_INVALID != border_color)
? ScanRight(x,y,xmax,color) : SearchRight(x,y,xmax,color))
if( MakeList() )
return -2;
MaxX = m_DibData.GetWidth()-1;
MaxY = m_DibData.GetHeight()-1;
PushLine(x,x,y,+1); /* Needed in one special case */
PushLine(x,x,y+1,-1);
while( m_pLineList ) {
PopLine(&ParentLeft,&ParentRight,&y,&dy);
y += dy;
if( y < 0 || MaxY < y )
continue;
if( m_bMemError )
continue;
if( m_bXSortOn && IsRevisit(ParentLeft,ParentRight,y) )
continue;
if( m_bSlowMode ) {
nKeyState = ::GetAsyncKeyState(VK_ESCAPE);
if( nKeyState < 0 )
break;
}
m_CurrentLine = y;
ChildLeft = FindLeft(ParentLeft,y,0,ThisColor)+1;
if( ChildLeft<=ParentLeft ) {
ChildRight = FindRight(ParentLeft,y,MaxX,ThisColor)-1;
if( ChildLeft == ChildRight )
SetPixel(ChildRight,y,fill_color);
else
DrawHorizontalLine(ChildLeft,ChildRight,y,fill_color);
#ifdef QUICKFILL_SLOW
if( m_bSlowMode && hWnd ) {
m_DibData.SetDIBits(pBitmap);
::InvalidateRect(hWnd,NULL,FALSE);
::UpdateWindow(hWnd);
}
#endif
if( ParentLeft-1<=ChildLeft && ChildRight<=ParentRight+1 ) {
PushLine(ChildLeft,ChildRight,y,dy);
}
else {
if( m_bXSortOn )
PushOpposite(ParentLeft,ParentRight,
ChildLeft,ChildRight,y,dy);
else
PushLine(ChildLeft,ChildRight,y,-dy);
PushLine(ChildLeft,ChildRight,y,dy);
}
++ChildRight;
}
else ChildRight = ParentLeft;
while( ChildRight < ParentRight ) {
ChildRight = SkipRight(ChildRight,y,ParentRight,ThisColor);
if( ChildRight<=ParentRight ) {
ChildLeft = ChildRight;
ChildRight = FindRight(ChildLeft,y,MaxX,ThisColor)-1;
if( ChildLeft == ChildRight )
SetPixel(ChildRight,y,fill_color);
else
DrawHorizontalLine(ChildLeft,ChildRight,y,fill_color);
if( m_bSlowMode && hWnd ) {
m_DibData.SetDIBits(pBitmap);
::InvalidateRect(hWnd,NULL,FALSE);
::UpdateWindow(hWnd);
}
if( ChildRight <= ParentRight+1 )
PushLine(ChildLeft,ChildRight,y,dy);
else {
if( m_bXSortOn )
PushOpposite(ParentLeft,ParentRight,
ChildLeft,ChildRight,y,dy);
else
PushLine(ChildLeft,ChildRight,y,-dy);
PushLine(ChildLeft,ChildRight,y,dy);
}
++ChildRight;
}
}
if( m_bXSortOn )
PushVisitedLine(ParentLeft,ParentRight,y);
}
FreeList();
m_DibData.SetDIBits(pBitmap);
m_DibData.DeleteObject();
return( m_bMemError?-2:0 );
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.