fork download
copy 
  1. /* ===== ===== =====
  2.  
  3. Theory of Programming
  4.  
  5. Snakes and Ladders Game - Steps for quickest way to finish
  6. http://t...content-available-to-author-only...g.com/2014/12/25/snakes-and-ladders-game-code/
  7. GitHub - https://g...content-available-to-author-only...b.com/VamsiSangam/theoryofprogramming
  8. Code Contributor - Vamsi Sangam
  9.  
  10. ===== ===== ===== */
  11.  
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14.  
  15. struct node {
  16. 	int val;
  17. 	struct node * next;
  18. };
  19.  
  20. // Adds a new edge, u --> v, to adjacencyList[u]
  21. struct node * addEdge(struct node * head, int num)
  22. {
  23. 	struct node * newNode = (struct node *) malloc(sizeof(struct node));
  24.  
  25.     newNode->val = num;
  26.     newNode->next = head;
  27.  
  28.     return newNode;
  29. }
  30.  
  31. void breadthFirstSearch(struct node * list[], int vertices, int parent[], int level[])
  32. {
  33. 	struct node * temp;
  34. 	int i, par, lev, flag = 1;
  35. 	// 'lev' represents the level to be assigned
  36. 	// 'par' represents the parent to be assigned
  37. 	// 'flag' used to indicate if graph is exhausted
  38.  
  39. 	lev = 0;
  40. 	level[1] = lev;
  41. 	// We start from node - 1
  42. 	// So, Node - 1 is at level 0
  43. 	// All immediate neighbours are at
  44. 	// level 1 and so on.
  45.  
  46. 	while (flag) {
  47. 		flag = 0;
  48. 		for (i = 1; i <= vertices; ++i) {
  49. 			if (level[i] == lev) {
  50. 				flag = 1;
  51. 				temp = list[i];
  52. 				par = i;
  53.  
  54. 				while (temp != NULL) {
  55. 					if (level[temp->val] != -1) {
  56. 						temp = temp->next;
  57. 						continue;
  58. 					}
  59.  
  60. 					level[temp->val] = lev + 1;
  61. 					parent[temp->val] = par;
  62. 					temp = temp->next;
  63. 				}
  64. 			}
  65. 		}
  66.  
  67. 		++lev;
  68. 	}
  69. }
  70.  
  71. // Replaces the value of an edge (u -->) v to (u --> v')
  72. // newNodes the entire list of adjacencyList[u] => O(|E|) operation
  73. // Here, "v" is stored as "oldVertex" and "v'" is stored as "newVertex"
  74. void replace(struct node * head, int num, int replacedNum)
  75. {
  76. 	struct node * p = head;
  77.  
  78. 	while (p->next != NULL) {
  79. 		if (p->val == num) {
  80. 			break;
  81. 		}
  82.  
  83. 		p = p->next;
  84. 	}
  85.  
  86. 	p->val = replacedNum;
  87. }
  88.  
  89. // A recursive procedure to print the shortest path. Recursively
  90. // looks at the parent of a vertex till the 'startVertex' is reached
  91. // Not used in main(), just for reference
  92. void printShortestPath(int parent[], int currentVertex, int startVertex)
  93. {
  94.     if (currentVertex == startVertex) {
  95.         printf("%d ", currentVertex);
  96.     } else if (parent[currentVertex] == 0) {
  97.         printShortestPath(parent, startVertex, startVertex);
  98.         printf("%d ", currentVertex);
  99.     } else {
  100.         printShortestPath(parent, parent[currentVertex], startVertex);
  101.         printf("%d ", currentVertex);
  102.     }
  103. }
  104.  
  105. int main()
  106. {
  107. 	int t;	// Test cases
  108.  
  109. 	scanf("%d", &t);
  110.  
  111. 	while (t--) {
  112. 		int vertices, edges, i, j, v1, v2;
  113.  
  114. 		vertices = 100;		// Assume it is a 100 checks board
  115. 		edges = 0;
  116.  
  117. 		struct node * list[vertices + 1];
  118. 		// This is the table of our Adjacency List
  119. 		// Each element holds a Linked List
  120. 		// In C++ it can be made to hold a vector too
  121. 		// in that case, the declaration would be -
  122. 		// vector< vector<int> > adjacency_list;
  123.  
  124. 		int parent[vertices + 1];
  125. 		// Each element of Parent Array holds the Node value of its parent
  126. 		int level[vertices + 1];
  127. 		// Each element of Level Array holds the Level value of that node
  128.  
  129. 		// Initialising our arrays
  130. 		for (i = 0; i <= vertices; ++i) {
  131. 			list[i] = NULL;
  132. 			parent[i] = 0;
  133. 			level[i] = -1;
  134. 		}
  135.  
  136. 		// Add normal edges representing movements by dice
  137. 		for (i = 1; i <= vertices; ++i) {
  138. 			for (j = 1; j <= 6 && j + i <= 100; ++j) {
  139. 				list[i] = addEdge(list[i], i + j);
  140. 				++edges;
  141. 			}
  142. 		}
  143.  
  144. 		int numLadders, numSnakes;
  145. 		char temp;
  146.  
  147. 		scanf("%d", &numLadders);
  148.  
  149. 		// Ladder Edges
  150. 		int ladders[numLadders][2];
  151.  
  152. 		for (i = 0; i < numLadders; ++i) {
  153. 			scanf("%d%c%d", &ladders[i][0], &temp, &ladders[i][1]);
  154.  
  155. 			j = ladders[i][0] - 6;
  156.  
  157. 			if (j < 1) {
  158. 				j = 1;
  159. 			}
  160.  
  161. 			for (; j < ladders[i][0]; ++j) {
  162. 				replace(list[j], ladders[i][0], ladders[i][1]);
  163. 			}
  164. 		}
  165.  
  166. 		scanf("%d", &numSnakes);
  167.  
  168. 		// Snakes Edges
  169. 		int snakes[numSnakes][2];
  170.  
  171. 		for (i = 0; i < numSnakes; ++i) {
  172. 			scanf("%d%c%d", &snakes[i][0], &temp, &snakes[i][1]);
  173.  
  174. 			j = snakes[i][0] - 6;
  175.  
  176. 			if (j < 0) {
  177. 				j = 0;
  178. 			}
  179.  
  180. 			for (; j < snakes[i][0]; ++j) {
  181. 				replace(list[j], snakes[i][0], snakes[i][1]);
  182. 			}
  183. 		}
  184.  
  185. 		breadthFirstSearch(list, vertices, parent, level);
  186. 		printf("%d\n", level[vertices]);
  187. 		printShortestPath(parent, 100, 1);
  188. 		printf("\n");
  189. 	}
  190.  
  191. 	return 0;
  192. }
Success #stdin #stdout 0s 9432KB
comments (?)
stdin
copy 
3
2
3 54
37 100
1
56 33
2
3 57
8 100
1
88 44
1
7 98
1
99 1
stdout
copy 
3
1 54 33 100 
2
1 2 100 
2
1 98 100
https://ideone.com/rpNCJf
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

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!