1
2#include <stdio.h>
3#include <stdlib.h>
4
5#define xIndex 3
6#define yIndex 3
7#define TRUE 1
8#define FALSE 0
9
**10**int startIndX = 0;
11int startIndY = 0;
12int endIndX = 2;
13int endIndY = 2;
14
15// Structure to construct final path
16typedef struct node {
17 int x;
18 int y;
19 int parentVal;
**20**} parent;
21
22typedef struct queue {
23 int x;
24 int y;
25 struct queue *next;
26} qnode;
27
28qnode *head;
29qnode *tail;
**30**
31// Neighbour index coordinates
32int neighbourIndex[4][2];
33int array[xIndex][yIndex];
34int visited[xIndex][yIndex];
35int row = xIndex - 1;
36int col = yIndex - 1;
37int startRow = 0;
38int startCol = 0;
39
**40**parent* parentArr[xIndex][yIndex];
41
42// Function declarations
43void neighbour(int sx, int sy);
44int isVisited(int x, int y);
45void markVisited(int x, int y);
46void markUnvisited(int x, int y);
47void markParent(int childX, int childY, int parentX, int parentY);
48void findPath(int startX, int startY, int endX, int endY);
49void enqueue(int x, int y);
**50**qnode* dequeue();
51int isQueueEmpty();
52void printPath(int x, int y);
53void freeQueue();
54void test1();
55
56
57void neighbour(int sx, int sy)
58{
59 int i = 0;
**60** int j = 0;
61
62 for (i = 0; i < 4; i++) {
63 for (j = 0; j < 2; j++) {
64 neighbourIndex[i][j] = -1;
65 }
66 }
67
68 i = 0; j = 0;
69
**70** if (sy - 1 >= startCol && sy - 1 <= col) {
71 neighbourIndex[i][0] = sx;
72 neighbourIndex[i][1] = sy - 1;
73 i++;
74 }
75
76 if (sx - 1 >= startRow && sx - 1 <= row) {
77 neighbourIndex[i][0] = sx - 1;
78 neighbourIndex[i][1] = sy;
79 i++;
**80** }
81
82 if (sy + 1 >= startCol && sy + 1 <= col) {
83 neighbourIndex[i][0] = sx;
84 neighbourIndex[i][1] = sy + 1;
85 i++;
86 }
87
88 if (sx + 1 >= startRow && sx + 1 <= row) {
89 neighbourIndex[i][0] = sx + 1;
**90** neighbourIndex[i][1] = sy;
91 i++;
92 }
93}
94
95int isVisited(int x, int y)
96{
97 return visited[x][y];
98}
99
**100**void markVisited(int x, int y)
101{
102 visited[x][y] = 1;
103}
104
105void markUnvisited(int x, int y)
106{
107 visited[x][y] = 0;
108}
109
**110**void markParent(int childX, int childY, int parentX, int parentY)
111{
112 parent* temp = (parent *)malloc(sizeof(parent));
113
114 if (temp == NULL) {
115 // Put ASSERT
116 }
117
118 temp->x = parentX;
119 temp->y = parentY;
**120** temp->parentVal = array[parentX][parentY];
121
122 parentArr[childX][childY] = temp;
123}
124
125void enqueue(int x, int y)
126{
127 qnode *temp = (qnode *)malloc(sizeof(qnode));
128 if (temp == NULL) {
129 // Put ASSERT
**130** }
131
132 temp->x = x;
133 temp->y = y;
134 temp->next = NULL;
135
136 tail->next = temp;
137
138 tail = temp;
139}
**140**
141qnode* dequeue()
142{
143 qnode *temp;
144
145 if (!isQueueEmpty()) {
146 temp = head->next;
147
148 if (temp == tail) {
149 tail = head;
**150** }
151 head->next = temp->next;
152 return temp;
153 }
154
155 return head->next;
156}
157
158int isQueueEmpty()
159{
**160** if (head->next == NULL) {
161 return TRUE;
162 }
163
164 return FALSE;
165}
166
167void freeQueue()
168{
169 qnode* temp;
**170**
171 while (head->next != NULL) {
172 temp = head->next;
173 head->next = head->next->next;
174
175 free (temp);
176 }
177
178}
179
**180**void printPath(int x, int y)
181{
182 parent *pInfo;
183
184 printf("Path:\n");
185 while (1) {
186 printf ("%d ", array[x][y]);
187
188 pInfo = parentArr[x][y];
189 x = pInfo->x;
**190** y = pInfo->y;
191
192 if (x == startIndX && y == startIndY) {
193 printf ("%d ", array[x][y]);
194 break;
195 }
196 }
197}
198
199void findPath(int startX, int startY, int endX, int endY)
**200**{
201 int i = 0;
202 int j = 0;
203 int x = startX;
204 int y = startY;
205 int neighbourX = startX;
206 int neighbourY = startY;
207 int reached = FALSE;
208 qnode *nextNode;
209
**210**
211 while (1) {
212 neighbour(x, y);
213
214 // Check, are we neighbour of destination?
215 for (i = 0; i < 4; i++) {
216 if (neighbourIndex[i][0] == endX && neighbourIndex[i][1] == endY) {
217 // Reached destination
218 neighbourX = neighbourIndex[i][0];
219 neighbourY = neighbourIndex[i][1];
**220** markParent(neighbourX, neighbourY, x, y);
221
222 reached = TRUE;
223 break;
224 } else {
225 // Validate neighbour
226 if (neighbourIndex[i][0] != -1) {
227 neighbourX = neighbourIndex[i][0];
228 neighbourY = neighbourIndex[i][1];
229 if (array[x][y] < array[neighbourX][neighbourY]) {
**230** // Mark neighbour index as visited
231 markVisited(x, y);
232 markVisited(neighbourX, neighbourY);
233
234 // Make me parent of neighbour index
235 markParent(neighbourX, neighbourY, x, y);
236
237 // Add neighbour to queue
238 enqueue(neighbourX, neighbourY);
239 }
**240** }
241 }
242 } // end of for
243
244 if (reached) {
245 // print path
246 printPath(endIndX, endIndY);
247 break;
248 }
249
**250** if (isQueueEmpty()) {
251 // If queue is empty then halt, no path found
252 printf ("No valid path exist");
253 break;
254 }
255
256 // Get next item from queue
257 nextNode = dequeue();
258 if (nextNode != NULL) {
259 x = nextNode->x;
**260** y = nextNode->y;
261
262 free (nextNode);
263 }
264 } // end of while
265}
266
267
268void test1()
269{
**270** int i = 0;
271 int j = 0;
272
273 array[0][0] = 1;
274 array[0][1] = 6;
275 array[0][2] = 8;
276 array[1][0] = 4;
277 array[1][1] = 7;
278 array[1][2] = 9;
279 array[2][0] = 5;
**280** array[2][1] = 2;
281 array[2][2] = 3;
282
283 printf("\n\n");
284 for (i = 0; i <= row; i++) {
285 for (j = 0; j <= col; j++) {
286 printf("%d ", array[i][j]);
287 }
288 printf("\n");
289 }
**290**
291 findPath(startIndX, startIndY, endIndX, endIndY);
292 freeQueue();
293}
294
295int main()
296{
297 head = (qnode*)malloc(sizeof(qnode));
298 head->x = -1;
299 head->y = -1;
**300** head->next = NULL;
301
302 tail = head;
303
304 test1();
305
306 return 0;
307}