当前位置: 动力学知识库 > 问答 > 编程问答 >

c - why this function always crashes?

问题描述:

Can anyone tell me why fillpool always crashes? Maybe there is an infinite recursion, but where?

#include <stdio.h>

#include <stdbool.h>

#define N 5

bool IsNotValidIndex(int Row , int Column)

{

if((Row >= N || Row < 0) || (Column >= N || Column < 0))

return true ;

return false ;

}

void fillpool(int row , int column , int picture[N][N])

{

if(IsNotValidIndex(row , column))

return ;

if(picture[row][column] == 0)

return ;

picture[row][column] = 2 ;

fillpool(row + 1 , column , picture) ;

fillpool(row - 1 , column , picture) ;

fillpool(row ,column + 1 , picture) ;

fillpool(row , column -1 , picture) ;

}

网友答案:

You have infinite recursion because you're setting the value of a row/col to "2" but then you check for it to be "0". So you're constantly setting the values to 2 over and over again. The infinite recursion happens because you're calling fillpool for "row+1" which will then do fillpool for "row-1" and so you get infinite recursion (and the same thing would happen with column+1 but you never reach there).

网友答案:

A code walk-through quickly makes the problem clear, the process is easily done by stepping the code in your debugger.

Let's say you call it with row = col = 2, this sets 2,2:

00000
00000
00200
00000
00000

Then you call fillpool(row + 1 , column , picture), which recurses until row is invalid:

00000
00000
00200
00200
00200

Then fillpool(row - 1 , column , picture) is called which sets 1,2:

00000
00200
00200
00200
00200

Then calls fillpool(row + 1 , column , picture), but that refers to 2,2 so you are exactly at your start condition, so will repeat the above sequence until the stack is exhausted.

The 4-way flood fill algorithm is thus (from https://en.wikipedia.org/wiki/Flood_fill):

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

You have incorrectly coded step 1 by testing for 0 but filling with 2:

if(picture[row][column] == 2) return ;

分享给朋友:
您可能感兴趣的文章:
随机阅读: