flood fill을 구현해보았습니다. - 다른 분의 코드에서 확장

이번에 소개해드릴 알고리즘은 Flood fill입니다.

한글 위키피디아 : http://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

영문 위키피디아 : http://en.wikipedia.org/wiki/Flood_fill

그리고 참고한 소스에서 클래스 모양까지 만든 것입니다.

floodfill_class_stack.cpp

test.in

/* * nonrecurcive */ #include <stdio.h> #include <stdlib.h> class FloodFill { typedef struct StackType { int x; int y; } Stack; private: int m_row, m_col; int *m_map; public: FloodFill() : m_row(0), m_col(0), m_map(NULL) { } ~FloodFill() { if (m_map) free(m_map); } void run() { loadFile(); printAll(); floodFill_rec(2, 0, 1, 0); printAll(); } void loadFile() { scanf("%d %d", &m_row, &m_col); m_map = (int*)malloc(sizeof(int)*m_row*m_col); for (int i=0;i<m_row;i++) { for (int j=0;j<m_col;j++) { scanf("%d", &m_map[i*m_row+j]); } } } void printAll() { for( int i=0;i<m_row;i++ ) { for( int j=0;j<m_col;j++ ) { printf("%3d", m_map[i*m_row + j]); } printf("\n"); } printf("\n"); } void floodFill_rec(int y, int x, int targetColor, int replaceColor) { Stack pos[m_row*m_col]; int sp = 0; pos[0].y = y; pos[0].x = x; while (sp >= 0) { y = pos[sp].y; x = pos[sp--].x; if (m_map[y*m_row+x] != targetColor || !(x >= 0 && x < m_col && y >= 0 && y < m_row)) { continue; } m_map[y*m_row+x] = replaceColor; // push pos[++sp].y = y-1; // up pos[sp].x = x; pos[++sp].y = y; // right pos[sp].x = x+1; pos[++sp].y = y+1; // down pos[sp].x = x; pos[++sp].y = y; // left pos[sp].x = x-1; } } }; int main() { FloodFill ff; ff.run(); return 0; }

문의사항이 있으시면 덧글로 달아주세요^^