shortest path

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

 

Leave a Reply