C solution, O(m*n*n) Runtime, O(m*n) Space


  • 0
    S
    /**
     * Return an array of arrays of size *returnSize.
     * The sizes of the arrays are returned as *columnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
    void copyMatrix(int **src, int **dst, int rowSize, int* colSizes)
    {
        int i, j;
        for(i=0; i<rowSize; i++)
        {
            for(j=0; j<colSizes[i]; j++)
            {
                dst[i][j] = src[i][j];
            }
        }
    }
    int** updateMatrix(int** matrix, int matrixRowSize, int *matrixColSizes, int** columnSizes, int* returnSize) {
        int i, j, num = 0, total=0;
        int *tmp;
        int ** ret = malloc(sizeof(int*) * matrixRowSize);
        int ** pre = malloc(sizeof(int*) * matrixRowSize);
        *columnSizes = (int *)calloc(matrixRowSize, sizeof(int));
        *returnSize = matrixRowSize;
        
        for(i=0; i < matrixRowSize; i++)
        {
            ret[i] = malloc(sizeof(int) * matrixColSizes[i]);
            pre[i] = malloc(sizeof(int) * matrixColSizes[i]);
            (*columnSizes)[i] = matrixColSizes[i];
            for(j=0; j<matrixColSizes[i]; j++){
                ret[i][j] = matrix[i][j] == 0 ? 0 : -1;
                pre[i][j] = matrix[i][j] == 0 ? 0 : -1;
            }
            total += matrixColSizes[i];
        }
        
        while(num < total){
            num = 0;
            for(i=0; i < matrixRowSize; i++)
            {
                for(j=0; j<matrixColSizes[i]; j++){
                    if(pre[i][j] >= 0){
                        num ++;
                        //update top
                        if(i > 0 && j < matrixColSizes[i-1]){
                            ret[i-1][j] = pre[i-1][j] == -1 || pre[i-1][j] >  pre[i][j] + 1 ? pre[i][j] + 1 : pre[i-1][j];
                        }
                        //update left
                        if(j > 0){
                            ret[i][j-1] = pre[i][j-1] == -1 || pre[i][j-1] > pre[i][j] + 1 ? pre[i][j] + 1 : pre[i][j-1];
                        }
                        //update bottom
                        if(i < matrixRowSize-1 && j < matrixColSizes[i+1]){
                            ret[i+1][j] = pre[i+1][j] == -1 || pre[i+1][j] >  pre[i][j] + 1 ? pre[i][j] + 1 : pre[i+1][j];
                        }
                        //update right
                        if(j < matrixColSizes[i]-1){
                            ret[i][j+1] = pre[i][j+1] == -1 || pre[i][j+1] > pre[i][j] + 1 ? pre[i][j] + 1 : pre[i][j+1];
                        }
                    }
                }
            }
            
            copyMatrix(ret, pre, matrixRowSize, matrixColSizes);
        }
        for(i=0; i < matrixRowSize; i++)
        {
            free(pre[i]); 
        }
        free(pre);
        
        return ret;
        
    }
    

Log in to reply
 

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