4 ms C solution


  • 0
    A
    int count;
    int **visited;
    int **map;
    
    void init(char** grid, int M, int N)
    {
        int i;
        int j;
        
        count = 0;
        visited = (int**)malloc(sizeof(int*)*(M+2));
        if(!visited)
        {
            exit(1);
        }
        for(i=0; i<M+2; i++)
        {
            visited[i] = (int*)malloc(sizeof(int)*(N+2));
            if(!visited[i])
            {
                exit(1);
            }
        }
        for(i=0; i<M+2; i++)
        {
            for(j=0; j<N+2; j++)
                visited[i][j] = 0;
        }
        map = (int**)malloc(sizeof(int*)*(M+2));
        if(!map)
        {
            exit(1);
        }
        for(i=0; i<M+2; i++)
        {
            map[i] = (int*)malloc(sizeof(int)*(N+2));
            if(!map[i])
            {
                exit(1);
            }
        }
        for(i=0; i<M+2; i++)
        {
            for(j=0; j<N+2; j++)
                map[i][j] = 0;
        }
        for(i=1; i<M+1; i++)
        {
            for(j=1; j<N+1; j++)
                map[i][j] = grid[i-1][j-1] - '0';
        }
    }
    
    void destroy(int M, int N)
    {
        int i;
        for(i=0; i<M+2; i++)
            free(visited[i]);
        for(i=0; i<M+2; i++)
            free(map[i]);
        free(visited);
        free(map);
        visited = NULL;
        map = NULL;
    }
    
    void find(int i, int j, int start)
    {
        int flag = 0;
        visited[i][j] = 1;
        if(map[i+1][j] && !visited[i+1][j])
        {
            flag = 1;
            visited[i+1][j] = 1;
            find(i+1, j, 0);
        }
        if(map[i][j+1] && !visited[i][j+1])
        {
            flag = 1;
            visited[i][j+1] = 1;
            find(i, j+1, 0);
        }
        if(map[i-1][j] && !visited[i-1][j])
        {
            flag = 1;
            visited[i-1][j] = 1;
            find(i-1, j, 0);
        }
        if(map[i][j-1] && !visited[i][j-1])
        {
            flag = 1;
            visited[i][j-1] = 1;
            find(i, j-1, 0);
        }
        if(start)
        {
            count++;
        }
    }
    
    void helper(int M, int N)
    {
        int i;
        int j;
        for(i=0; i<M; i++)
        {
            for(j=0; j<N; j++)
            {
                if(map[i+1][j+1])
                {
                    if(!visited[i+1][j+1])
                    {
                        find(i+1, j+1, 1);
                    }
                }
            }
        }
    }
    
    int numIslands(char** grid, int gridRowSize, int gridColSize) {
        init(grid, gridRowSize, gridColSize);
        helper(gridRowSize, gridColSize);
        destroy(gridRowSize, gridColSize);
        return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.