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

1   6   8   
4   7   9   
5   2   3   
Path:
3 9 7 4 1
https://ideone.com/0oLlT1
Graph BFS in ascending order
language:
C (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!