https://www.careercup.com/question?id=5722862468988928
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <unistd.h> #include <time.h> enum { G, O, W, }; struct position { int x, y; int type; int distance; void *visited; }; #define QUEUE_SIZE 100 #define ROW 5 #define COL 4 struct position matrix[ROW][COL]; struct queue { struct position *entries[QUEUE_SIZE]; int head, tail; }; void init_queue(struct queue *q) { q->head = q->tail = 0; } int empty(struct queue *q) { return (q->head == q->tail); } void enqueue(struct queue *q, struct position *p) { int tail = q->tail; q->entries[tail] = p; q->tail = (q->tail + 1) % QUEUE_SIZE; } struct position *dequeue(struct queue *q) { struct position *p; p = q->entries[q->head]; q->head = (q->head + 1) % QUEUE_SIZE; return p; } struct position *up(struct position *p) { if (p->x == 0) return NULL; return &matrix[p->x - 1][p->y]; } struct position *down(struct position *p) { if (p->x == ROW - 1) return NULL; return &matrix[p->x + 1][p->y]; } struct position *left(struct position *p) { if (p->y == 0) return NULL; return &matrix[p->x][p->y - 1]; } struct position *right(struct position *p) { if (p->y == COL - 1) return NULL; return &matrix[p->x][p->y + 1]; } void check_direction(struct position *p, struct position *guard, struct queue *q) { int distance = p->distance + 1; if (!guard || guard->type != O || guard->visited == p) return; if (distance < guard->distance) { guard->distance = distance; enqueue(q, guard); } guard->visited = p; } void one_guard_bfs(struct position *guard) { struct queue *q, _q; q = &_q; init_queue(q); guard->distance = 0; guard->visited = guard; enqueue(q, guard); while (!empty(q)) { guard = dequeue(q); check_direction(guard, up(guard), q); check_direction(guard, down(guard), q); check_direction(guard, left(guard), q); check_direction(guard, right(guard), q); } } void all_guards_bfs(struct position p[ROW][COL], int m, int n) { int i, j; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (p[i][j].type == G) one_guard_bfs(&p[i][j]); } int main() { int type[ROW][COL] = { {O, W, G, W}, {O, G, O, G}, {O, G, O, W}, {W, O, O, O}, {G, O, O, O}, }; int i, j; for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) { matrix[i][j].type = type[i][j]; matrix[i][j].x = i; matrix[i][j].y = j; matrix[i][j].distance = 9999; } } all_guards_bfs(matrix, ROW, COL); for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) { if (matrix[i][j].type == O) printf("%d, %d: %d\n", i, j, matrix[i][j].distance); } } return 0; }