Problem description

leetcode1901

Train of thought

The shortest path problem is the algorithm of BFS, through the queue, the current position in the queue, and then pop up a queue element, the element may reach the position of the queue, so layer by layer, until the target location is found, through the shortest path.

code

Queue initialization

Because you are implementing BFS with queues, you define the queue function first

// create a node typedef struct dataType{int x; int y; }DType; struct Node{ DType val; struct Node* next; }; Struct Queue{struct Node* head; struct Node* tail; int size; }; typedef struct Queue* Qpinter; typedef struct Node* nodePr; // Create queue QpintercreatQueue()
{
    Qpinter tempQ = (Qpinter)malloc(sizeof(struct Queue));
    if(tempQ == NULL)
        return NULL;
    tempQ->head = NULL;
    tempQ->tail = NULL;
    tempQ->size = 0;
    returntempQ; Qpinter insetQueue(Qpinter q, DType a) {nodePr tempN = (nodePr)malloc(sizeof(struct Node)); tempN->val = a; tempN->next = NULL;if(q->head == NULL)
    {
        q->tail = tempN;
        q->head = tempN;
    }
    else{
        q->tail->next = tempN;
    }
    q->tail = tempN;
    q->size++;
    returnq; } // delete the element DType deleQueue(Qpinter q) {DType res; nodePr temp;if(q->head == NULL)
        exit(0);
    if(q->head == q->tail)
    {
        res = q->head->val;
        temp = q->head;
        q->head = NULL;
        q->tail = NULL;
    }
    else{
        res = q->head->val;
        temp = q->head;
        q->head = q->head->next;
    }
    free(temp);
    q->size--;
    returnres; Void destoryQ(Qpinter q) {nodePr temp;while(q->head != NULL)
    {
        temp = q->head;
        q->head = q->head->next;
        free(temp);
    }
}
Copy the code

The main program

int shortestPathBinaryMatrix(int** grid, int gridSize, int* gridColSize){ Qpinter Q1 = creatQueue(); DType temp = {0, 0}; // We can initialize some boundary conditions directly according to the structure orderif(grid[0][0] == 1 || grid[gridSize - 1][*gridColSize - 1] == 1)
        return- 1;if(gridSize == 1 && *gridColSize == 1) return1; Int res = 1; int mark[gridSize][*gridColSize]; insetQueue(Q1, temp); Mark [temp. X][temp. X] = 1; // If the queue is not empty, go straight down. If the queue is empty, go straight downwhile(Q1->head ! Int size = Q1->size; int size = Q1->size;for(int i = 0; i < size; i++){ temp = deleQueue(Q1); // mark[x][y] = 1; Int x = temp. X; int y = temp.y; / / relative position calculating int destion [8] [2] = {{x 1, y - 1}, {1 x, y}, {x 1, y + 1}, {x, y, 1}, {x, y + 1}, {x + 1, y - 1}, {x + 1, y}, {x + 1, y + 1}};for(int j = 0; j < 8; j++) { int x = destion[j][0]; int y = destion[j][1]; // The array is out of boundsif(x < 0 || x >= gridSize || y < 0 || y >= *gridColSize)
                    continue; / / foundif(x == gridSize - 1 && y == *gridColSize - 1) returnres + 1; // Already goneif(mark[x][y] == 1) 
                    continue; // The road is blockedif(grid[x][y] == 1) continue; temp.x = x; temp.y = y; mark[temp.x][temp.y] = 1; InsetQueue (Q1, temp); insetQueue(Q1, temp); } } res++; }return- 1; }Copy the code

conclusion

• Time complexity O(n):n is the number of elements
• Space complexity O(K):K is the maximum length of the queue