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;
}