알고리즘:bfs 색칠하기

알고리즘:bfs 색칠하기

0으로 둘러 쌓인 1로 이루어진 곳에 다른 숫자 채우기

bfs3.txt

7
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0

------------------------------------------------

#include <stdio.h>

typedef struct _path{
    int x;
    int y;
    int length;
} Path;

Path que[100];

int n;
int map[100][100];
int front = 0;
int rear = 0;
int count = 1;
int ans = 100;
void enque(int x, int y, int c){
    que[rear].x = x;
    que[rear].y = y;
    que[rear].length = c +1;
    rear ++;

    map[y][x] = c;

}
void bfs3(int x, int y, int c){
        map[y][x] = c;

        que[rear].x = x;
        que[rear].y = y;
        que[rear].length = count;

        rear++;
        Path path;
        while(front < rear){
            path  = que[front++];

            if (path.y -1 >= 0 && map[path.y -1][path.x] == 1){
                enque(path.x, path.y -1, c);
            }
            if (path.y +1 < n && map[path.y +1][path.x] == 1){
                enque(path.x, path.y+1, c);
            }
            //left
            if (path.x-1 >= 0 && map[path.y][path.x-1] == 1){
                enque(path.x-1, path.y,c);
            }
            //right
            if (path.x+1 < n  && map[path.y ][path.x+1] == 1){
                enque(path.x+1, path.y, c);
            }
        }
}

void printmap(){
    printf("-------------------------------\n");
     for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                printf("%d", map[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    int start;
    int v1, v2;


    freopen("bfs3.txt","r",stdin);

    scanf("%d", &n);


    for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                scanf("%d", &map[i][j]);
        }
    }

    printmap();

    int color = 2;
    for (int i = 0; i < n ; i ++){
        for(int j = 0; j < n ; j++){
            if(map[i][j] == 1){
                bfs3(j,i, color++);
            }
        }
    }

    printf("answer %d\n", color-2);
    printmap();

    return 0;
}