c语言求岛屿数量

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX_POINT_NUM 1024*1024

typedef struct {
    int x;
    int y;
} point;

typedef struct {
        int x[MAX_POINT_NUM];
        int y[MAX_POINT_NUM];
        int top;
} stack_node, *stack;

stack stack_new()
{
    stack s = (stack)malloc(sizeof(stack_node));

    s->top = -1;

    return s;
}

void stack_free(stack s)
{
    free(s);
}

void stack_clear(stack s)
{
    s->top = -1;
}

short stack_is_empty(stack s)
{
    if(s->top < 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

short stack_push(stack s, int x, int y)
{
    if(s->top >= MAX_POINT_NUM - 1)
    {
        return 0;
    }
    else
    {
        s->top++;

        s->x[s->top] = x;
        s->y[s->top] = y;

        return 1;
    }
}

short stack_pop(stack s)
{
    if(s->top < 0)
    {
        return 0;
    }

    s->top--;

    return 1;
}

point stack_top(stack s)
{
    point p;

    p.x = s->x[s->top];
    p.y = s->y[s->top];

    return p;
}

int get_next(int **map, int n, int m, int *x, int *y)
{
    if(*x - 1 >= 0 && map[*x-1][*y] == 1)
    {
        map[*x-1][*y] = 0;

        *x = (*x-1);

        return 0;
    }

    if(*x + 1 < n && map[*x+1][*y] == 1)
    {
        map[*x+1][*y] = 0;

        *x = (*x+1);

        return 0;
    }

    if(*y - 1 >= 0 && map[*x][*y-1] == 1)
    {
        map[*x][*y-1] = 0;

        *y = (*y-1);

        return 0;
    }

    if(*y + 1 < m && map[*x][*y+1] == 1)
    {
        map[*x][*y+1] = 0;

        *y = (*y+1);

        return 0;
    }

    return -1;
}

int get_one(int **map, int n, int m, int x, int y)
{
    stack s = stack_new();
    point a;

    if(map[x][y] == 0)
    {
        stack_free(s);

        return 0;
    }

    a.x = x;
    a.y = y;

    stack_push(s, x, y);

    while(!stack_is_empty(s))
    {
        a = stack_top(s);

        x = a.x;
        y = a.y;

        if(get_next(map, n, m, &x, &y) == 0)
        {
            a.x = x;
            a.y = y;

            stack_push(s, x, y);
        }
        else
        {
            stack_pop(s);
        }
    }

    stack_free(s);

    return 1;
}

int get_num(int **map, int n, int m)
{
    int i, j, k = 0;

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            k += get_one(map, n, m, i, j);
        }
    }

    return k;
}

int main()
{
    int a[5][5] = {{1,1,0,0,0}, {0,1,0,1,1}, {0,0,0,1,1}, {0,0,0,0,0}, {0,0,1,1,1}};
    int *map[5];
    int i;

    for(i=0; i<5; i++)
    {
        map[i] = a[i];
    }

    printf("%d\n", get_num(map, 5, 5));

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
3