Brutal-force C solution that beats 100% (explanation)


  • 0
    F

    My C solution is almost by brutal-force. It temporarily beats 100% of the submissions. Knowing that there are many smart solutions, I hope mine serves as an alternative. Explanation is in the code.

    /*  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(). */
    
    /*  Suppose the cell we are concerned with are at the center of the diamond.
        This diamond shows what the nearest distance d would be if a nearest 0 is found at the corresponding place.
        Therefore, we should search from d = 0 to d = 1 to d = 2 ...
        For a fixed distance d, we search clockwise, from (A) to (B) to (C) to (D) then back to (A).
    
                           (A)
                            3
                        3   2   3
                    3   2   1   2   3
            (D) 3   2   1   0   1   2   3 (B)
                    3   2   1   2   3
                        3   2   3
                            3
                           (C)
    
        Of course, the search is done respecting the boundaries of the matrix.
        It appears that some "smart" jumps may be attempted. For example, stop to move up further if ceiling has been touched.
        But the benefit of checking may not outweigh the cost in terms of speed. I have tried.
        
        In what follows, (h, k) is the coordinate for the cell that is being searched.
        And dh[4], dk[4], ch[4], ck[4] are variables controlling the clockwise movement.
        If you don't like them, you may well discard them, and expand that one block into four, which lengthens the code but shortens the run time. */
    
    int **updateMatrix(int **matrix, int matrixRowSize, int matrixColSize, int **columnSizes, int *returnSize)
    {
        *returnSize = matrixRowSize;
        *columnSizes = (int *)calloc(matrixRowSize, sizeof(int));    
        int **dist = (int **)calloc(matrixRowSize, sizeof(int *));
        for (int i = 0; i < matrixRowSize; ++i) {
            dist[i] = (int *)calloc(matrixColSize, sizeof(int));
            (*columnSizes)[i] = matrixColSize;
        }
    
        int dh[4] = { 1, 1, -1, -1 }, dk[4] = { 1, -1, -1, 1 }, ch[4] = { 1, 0, 1, 0 }, ck[4] = { 0, 1, 0, 1 };
        
        for (int i = 0; i < matrixRowSize; ++i)
        for (int j = 0; j < matrixColSize; ++j) {
            if (matrix[i][j] == 0) {
                dist[i][j] = 0;
                continue;
            }
            for (int d = 1; ; ++d) {
                int h = i - d, k = j;
                bool found = false;
                for (int q = 0; q < 4; ++q) {                    
                    for (; ch[q] &&  h != i || ck[q] && k != j; h += dh[q], k += dk[q]) {
                        if (h < 0 || h >= matrixRowSize || k < 0 || k >= matrixColSize)
                            continue;
                        if (matrix[h][k] == 0) {
                            dist[i][j] = d;
                            found = true;
                            break;
                        }
                    }
                    if (found)
                        break;                    
                }
                if (found)
                    break;
            }
        }
        return dist;
    }
    

    0_1504106727524_1.PNG


Log in to reply
 

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