C语言 | Leetcode C语言接雨水II

题目：

题解：

typedef struct{
    int row;
    int column;
    int height;
} Element;

struct Pri_Queue;
typedef struct Pri_Queue *P_Pri_Queue;
typedef Element Datatype;

struct Pri_Queue{
    int n;
    Datatype *pri_qu;
};

/*优先队列插入*/
P_Pri_Queue add_pri_queue(P_Pri_Queue pq, Datatype x){


    int i;

    if(pq->n == 0){
        pq->pri_qu[0] = x; pq->n ++; return(pq);
    }
    else{
        for(i = pq->n; (i > 0) && (x.height < pq->pri_qu[(i - 1) / 2].height); i = (i - 1) / 2){
            pq->pri_qu[i] = pq->pri_qu[(i - 1) / 2];
        }
    }

    pq->pri_qu[i] = x;
    pq->n ++;
    return(pq);
}

/*优先队列删除*/
P_Pri_Queue del_pri_queue(P_Pri_Queue pq){
    int i = 0;

    if(pq->n > 1){
        while(i <= (pq->n - 2) / 2){
            if((pq->pri_qu[pq->n - 1].height > pq->pri_qu[2 * i + 1].height) || \
                ((2 * i + 2 <= pq->n - 1) && (pq->pri_qu[pq->n - 1].height > pq->pri_qu[2 * i + 2].height))){

                if(2 * i + 2 <= pq->n - 1){
                    if(pq->pri_qu[2 * i + 1].height > pq->pri_qu[2 * i + 2].height){
                        pq->pri_qu[i] = pq->pri_qu[2 * i + 2];
                        i = 2 * i + 2;
                    }
                    else{
                        pq->pri_qu[i] = pq->pri_qu[2 * i + 1];
                        i = 2 * i + 1;
                    }
                }
                else{
                    pq->pri_qu[i] = pq->pri_qu[2 * i + 1];
                    i = 2 * i + 1;
                }
            }
            else{
                pq->pri_qu[i] = pq->pri_qu[pq->n - 1];
                pq->n --;
                return(pq);
            }
        }
    }

    pq->pri_qu[i] = pq->pri_qu[pq->n - 1];
    pq->n --;
    return(pq);
}

int trapRainWater(int** heightMap, int heightMapSize, int* heightMapColSize){
    if((heightMapSize < 3) || (*heightMapColSize < 3)) return(0);

    int Used_heightMap[112][112] = {0}, i, j, ans = 0;
    int direct[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    Datatype x;


    P_Pri_Queue pq;
    pq = (P_Pri_Queue)malloc(sizeof(struct Pri_Queue));
    pq->n = 0; pq->pri_qu = (Datatype*)malloc(sizeof(Datatype) * heightMapSize * (*heightMapColSize));

    for(i = 0; i < heightMapSize + 2; i ++) Used_heightMap[i][0] = 1;
    for(i = 0; i < heightMapSize + 2; i ++) Used_heightMap[i][1] = 1;
    for(i = 0; i < heightMapSize + 2; i ++) Used_heightMap[i][*heightMapColSize] = 1;
    for(i = 0; i < heightMapSize + 2; i ++) Used_heightMap[i][*heightMapColSize + 1] = 1;
    for(j = 0; j < *heightMapColSize + 2; j ++) Used_heightMap[0][j] = 1;
    for(j = 0; j < *heightMapColSize + 2; j ++) Used_heightMap[1][j] = 1;
    for(j = 0; j < *heightMapColSize + 2; j ++) Used_heightMap[heightMapSize][j] = 1;
    for(j = 0; j < *heightMapColSize + 2; j ++) Used_heightMap[heightMapSize + 1][j] = 1;

    for(i = 1; i < heightMapSize - 1; i ++){
        x.row = i; x.column = 0; x.height = heightMap[i][0];
        add_pri_queue(pq, x);
    }
    for(i = 1; i < heightMapSize - 1; i ++){
        x.row = i; x.column = *heightMapColSize - 1; x.height = heightMap[i][*heightMapColSize - 1];
        add_pri_queue(pq, x);
    }
    for(j = 1; j < *heightMapColSize - 1; j ++){
        x.row = 0; x.column = j; x.height = heightMap[0][j];
        add_pri_queue(pq, x);
    }
    for(j = 1; j < *heightMapColSize - 1; j ++){
        x.row = heightMapSize - 1; x.column = j; x.height = heightMap[heightMapSize - 1][j];
        add_pri_queue(pq, x);
    }

    while(pq->n > 0){
        for(i = 0; i < 4; i ++){
            if(Used_heightMap[pq->pri_qu[0].row + 1 + direct[i][0]][pq->pri_qu[0].column + 1 + direct[i][1]] == 0){
                if(heightMap[pq->pri_qu[0].row + direct[i][0]][pq->pri_qu[0].column + direct[i][1]] < pq->pri_qu[0].height){
                    ans += pq->pri_qu[0].height - heightMap[pq->pri_qu[0].row + direct[i][0]][pq->pri_qu[0].column + direct[i][1]];
                    x.height = pq->pri_qu[0].height;
                }
                else{x.height = heightMap[pq->pri_qu[0].row + direct[i][0]][pq->pri_qu[0].column + direct[i][1]];}

                x.row = pq->pri_qu[0].row + direct[i][0]; x.column = pq->pri_qu[0].column + direct[i][1];
                add_pri_queue(pq, x);
                Used_heightMap[pq->pri_qu[0].row + 1 + direct[i][0]][pq->pri_qu[0].column + 1 + direct[i][1]] = 1;
            }
        }

        //printf("row = %d, column =  %d, height = %d, n = %d\n", pq->pri_qu[0].row, pq->pri_qu[0].column, pq->pri_qu[0].height, pq->n);
        del_pri_queue(pq);
        //printf("row = %d, column =  %d, height = %d, n = %d\n", pq->pri_qu[0].row, pq->pri_qu[0].column, pq->pri_qu[0].height, pq->n);
    }

    return(ans);
}