/* ===== ===== =====
Theory of Programming
Snakes and Ladders Game - Steps for quickest way to finish
http://t...content-available-to-author-only...g.com/2014/12/25/snakes-and-ladders-game-code/
GitHub - https://g...content-available-to-author-only...b.com/VamsiSangam/theoryofprogramming
Code Contributor - Vamsi Sangam
===== ===== ===== */
#include <stdio.h>
#include <stdlib.h>
struct node {
int val;
struct node * next;
};
// Adds a new edge, u --> v, to adjacencyList[u]
struct node * addEdge(struct node * head, int num)
{
struct node
* newNode
= (struct node
*) malloc(sizeof(struct node
));
newNode->val = num;
newNode->next = head;
return newNode;
}
void breadthFirstSearch(struct node * list[], int vertices, int parent[], int level[])
{
struct node * temp;
int i, par, lev, flag = 1;
// 'lev' represents the level to be assigned
// 'par' represents the parent to be assigned
// 'flag' used to indicate if graph is exhausted
lev = 0;
level[1] = lev;
// We start from node - 1
// So, Node - 1 is at level 0
// All immediate neighbours are at
// level 1 and so on.
while (flag) {
flag = 0;
for (i = 1; i <= vertices; ++i) {
if (level[i] == lev) {
flag = 1;
temp = list[i];
par = i;
while (temp != NULL) {
if (level[temp->val] != -1) {
temp = temp->next;
continue;
}
level[temp->val] = lev + 1;
parent[temp->val] = par;
temp = temp->next;
}
}
}
++lev;
}
}
// Replaces the value of an edge (u -->) v to (u --> v')
// newNodes the entire list of adjacencyList[u] => O(|E|) operation
// Here, "v" is stored as "oldVertex" and "v'" is stored as "newVertex"
void replace(struct node * head, int num, int replacedNum)
{
struct node * p = head;
while (p->next != NULL) {
if (p->val == num) {
break;
}
p = p->next;
}
p->val = replacedNum;
}
// A recursive procedure to print the shortest path. Recursively
// looks at the parent of a vertex till the 'startVertex' is reached
// Not used in main(), just for reference
void printShortestPath(int parent[], int currentVertex, int startVertex)
{
if (currentVertex == startVertex) {
} else if (parent[currentVertex] == 0) {
printShortestPath(parent, startVertex, startVertex);
} else {
printShortestPath(parent, parent[currentVertex], startVertex);
}
}
int main()
{
int t; // Test cases
while (t--) {
int vertices, edges, i, j, v1, v2;
vertices = 100; // Assume it is a 100 checks board
edges = 0;
struct node * list[vertices + 1];
// This is the table of our Adjacency List
// Each element holds a Linked List
// In C++ it can be made to hold a vector too
// in that case, the declaration would be -
// vector< vector<int> > adjacency_list;
int parent[vertices + 1];
// Each element of Parent Array holds the Node value of its parent
int level[vertices + 1];
// Each element of Level Array holds the Level value of that node
// Initialising our arrays
for (i = 0; i <= vertices; ++i) {
list[i] = NULL;
parent[i] = 0;
level[i] = -1;
}
// Add normal edges representing movements by dice
for (i = 1; i <= vertices; ++i) {
for (j = 1; j <= 6 && j + i <= 100; ++j) {
list[i] = addEdge(list[i], i + j);
++edges;
}
}
int numLadders, numSnakes;
char temp;
scanf("%d", &numLadders
);
// Ladder Edges
int ladders[numLadders][2];
for (i = 0; i < numLadders; ++i) {
scanf("%d%c%d", &ladders
[i
][0], &temp
, &ladders
[i
][1]);
j = ladders[i][0] - 6;
if (j < 1) {
j = 1;
}
for (; j < ladders[i][0]; ++j) {
replace(list[j], ladders[i][0], ladders[i][1]);
}
}
// Snakes Edges
int snakes[numSnakes][2];
for (i = 0; i < numSnakes; ++i) {
scanf("%d%c%d", &snakes
[i
][0], &temp
, &snakes
[i
][1]);
j = snakes[i][0] - 6;
if (j < 0) {
j = 0;
}
for (; j < snakes[i][0]; ++j) {
replace(list[j], snakes[i][0], snakes[i][1]);
}
}
breadthFirstSearch(list, vertices, parent, level);
printf("%d\n", level
[vertices
]); printShortestPath(parent, 100, 1);
}
return 0;
}
LyogPT09PT0gPT09PT0gPT09PT0KClRoZW9yeSBvZiBQcm9ncmFtbWluZwoKU25ha2VzIGFuZCBMYWRkZXJzIEdhbWUgLSBTdGVwcyBmb3IgcXVpY2tlc3Qgd2F5IHRvIGZpbmlzaApodHRwOi8vdC4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZy5jb20vMjAxNC8xMi8yNS9zbmFrZXMtYW5kLWxhZGRlcnMtZ2FtZS1jb2RlLwpHaXRIdWIgLSBodHRwczovL2cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmIuY29tL1ZhbXNpU2FuZ2FtL3RoZW9yeW9mcHJvZ3JhbW1pbmcKQ29kZSBDb250cmlidXRvciAtIFZhbXNpIFNhbmdhbQoKPT09PT0gPT09PT0gPT09PT0gKi8KCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CgpzdHJ1Y3Qgbm9kZSB7CglpbnQgdmFsOwoJc3RydWN0IG5vZGUgKiBuZXh0Owp9OwoKLy8gQWRkcyBhIG5ldyBlZGdlLCB1IC0tPiB2LCB0byBhZGphY2VuY3lMaXN0W3VdCnN0cnVjdCBub2RlICogYWRkRWRnZShzdHJ1Y3Qgbm9kZSAqIGhlYWQsIGludCBudW0pCnsKCXN0cnVjdCBub2RlICogbmV3Tm9kZSA9IChzdHJ1Y3Qgbm9kZSAqKSBtYWxsb2Moc2l6ZW9mKHN0cnVjdCBub2RlKSk7CgogICAgbmV3Tm9kZS0+dmFsID0gbnVtOwogICAgbmV3Tm9kZS0+bmV4dCA9IGhlYWQ7CgogICAgcmV0dXJuIG5ld05vZGU7Cn0KCnZvaWQgYnJlYWR0aEZpcnN0U2VhcmNoKHN0cnVjdCBub2RlICogbGlzdFtdLCBpbnQgdmVydGljZXMsIGludCBwYXJlbnRbXSwgaW50IGxldmVsW10pCnsKCXN0cnVjdCBub2RlICogdGVtcDsKCWludCBpLCBwYXIsIGxldiwgZmxhZyA9IDE7CgkvLyAnbGV2JyByZXByZXNlbnRzIHRoZSBsZXZlbCB0byBiZSBhc3NpZ25lZAoJLy8gJ3BhcicgcmVwcmVzZW50cyB0aGUgcGFyZW50IHRvIGJlIGFzc2lnbmVkCgkvLyAnZmxhZycgdXNlZCB0byBpbmRpY2F0ZSBpZiBncmFwaCBpcyBleGhhdXN0ZWQKCglsZXYgPSAwOwoJbGV2ZWxbMV0gPSBsZXY7CgkvLyBXZSBzdGFydCBmcm9tIG5vZGUgLSAxCgkvLyBTbywgTm9kZSAtIDEgaXMgYXQgbGV2ZWwgMAoJLy8gQWxsIGltbWVkaWF0ZSBuZWlnaGJvdXJzIGFyZSBhdAoJLy8gbGV2ZWwgMSBhbmQgc28gb24uCgoJd2hpbGUgKGZsYWcpIHsKCQlmbGFnID0gMDsKCQlmb3IgKGkgPSAxOyBpIDw9IHZlcnRpY2VzOyArK2kpIHsKCQkJaWYgKGxldmVsW2ldID09IGxldikgewoJCQkJZmxhZyA9IDE7CgkJCQl0ZW1wID0gbGlzdFtpXTsKCQkJCXBhciA9IGk7CgoJCQkJd2hpbGUgKHRlbXAgIT0gTlVMTCkgewoJCQkJCWlmIChsZXZlbFt0ZW1wLT52YWxdICE9IC0xKSB7CgkJCQkJCXRlbXAgPSB0ZW1wLT5uZXh0OwoJCQkJCQljb250aW51ZTsKCQkJCQl9CgoJCQkJCWxldmVsW3RlbXAtPnZhbF0gPSBsZXYgKyAxOwoJCQkJCXBhcmVudFt0ZW1wLT52YWxdID0gcGFyOwoJCQkJCXRlbXAgPSB0ZW1wLT5uZXh0OwoJCQkJfQoJCQl9CgkJfQoKCQkrK2xldjsKCX0KfQoKLy8gUmVwbGFjZXMgdGhlIHZhbHVlIG9mIGFuIGVkZ2UgKHUgLS0+KSB2IHRvICh1IC0tPiB2JykKLy8gbmV3Tm9kZXMgdGhlIGVudGlyZSBsaXN0IG9mIGFkamFjZW5jeUxpc3RbdV0gPT4gTyh8RXwpIG9wZXJhdGlvbgovLyBIZXJlLCAidiIgaXMgc3RvcmVkIGFzICJvbGRWZXJ0ZXgiIGFuZCAidiciIGlzIHN0b3JlZCBhcyAibmV3VmVydGV4Igp2b2lkIHJlcGxhY2Uoc3RydWN0IG5vZGUgKiBoZWFkLCBpbnQgbnVtLCBpbnQgcmVwbGFjZWROdW0pCnsKCXN0cnVjdCBub2RlICogcCA9IGhlYWQ7CgoJd2hpbGUgKHAtPm5leHQgIT0gTlVMTCkgewoJCWlmIChwLT52YWwgPT0gbnVtKSB7CgkJCWJyZWFrOwoJCX0KCgkJcCA9IHAtPm5leHQ7Cgl9CgoJcC0+dmFsID0gcmVwbGFjZWROdW07Cn0KCi8vIEEgcmVjdXJzaXZlIHByb2NlZHVyZSB0byBwcmludCB0aGUgc2hvcnRlc3QgcGF0aC4gUmVjdXJzaXZlbHkKLy8gbG9va3MgYXQgdGhlIHBhcmVudCBvZiBhIHZlcnRleCB0aWxsIHRoZSAnc3RhcnRWZXJ0ZXgnIGlzIHJlYWNoZWQKLy8gTm90IHVzZWQgaW4gbWFpbigpLCBqdXN0IGZvciByZWZlcmVuY2UKdm9pZCBwcmludFNob3J0ZXN0UGF0aChpbnQgcGFyZW50W10sIGludCBjdXJyZW50VmVydGV4LCBpbnQgc3RhcnRWZXJ0ZXgpCnsKICAgIGlmIChjdXJyZW50VmVydGV4ID09IHN0YXJ0VmVydGV4KSB7CiAgICAgICAgcHJpbnRmKCIlZCAiLCBjdXJyZW50VmVydGV4KTsKICAgIH0gZWxzZSBpZiAocGFyZW50W2N1cnJlbnRWZXJ0ZXhdID09IDApIHsKICAgICAgICBwcmludFNob3J0ZXN0UGF0aChwYXJlbnQsIHN0YXJ0VmVydGV4LCBzdGFydFZlcnRleCk7CiAgICAgICAgcHJpbnRmKCIlZCAiLCBjdXJyZW50VmVydGV4KTsKICAgIH0gZWxzZSB7CiAgICAgICAgcHJpbnRTaG9ydGVzdFBhdGgocGFyZW50LCBwYXJlbnRbY3VycmVudFZlcnRleF0sIHN0YXJ0VmVydGV4KTsKICAgICAgICBwcmludGYoIiVkICIsIGN1cnJlbnRWZXJ0ZXgpOwogICAgfQp9CgppbnQgbWFpbigpCnsKCWludCB0OwkvLyBUZXN0IGNhc2VzCgoJc2NhbmYoIiVkIiwgJnQpOwoKCXdoaWxlICh0LS0pIHsKCQlpbnQgdmVydGljZXMsIGVkZ2VzLCBpLCBqLCB2MSwgdjI7CgoJCXZlcnRpY2VzID0gMTAwOwkJLy8gQXNzdW1lIGl0IGlzIGEgMTAwIGNoZWNrcyBib2FyZAoJCWVkZ2VzID0gMDsKCgkJc3RydWN0IG5vZGUgKiBsaXN0W3ZlcnRpY2VzICsgMV07CgkJLy8gVGhpcyBpcyB0aGUgdGFibGUgb2Ygb3VyIEFkamFjZW5jeSBMaXN0CgkJLy8gRWFjaCBlbGVtZW50IGhvbGRzIGEgTGlua2VkIExpc3QKCQkvLyBJbiBDKysgaXQgY2FuIGJlIG1hZGUgdG8gaG9sZCBhIHZlY3RvciB0b28KCQkvLyBpbiB0aGF0IGNhc2UsIHRoZSBkZWNsYXJhdGlvbiB3b3VsZCBiZSAtCgkJLy8gdmVjdG9yPCB2ZWN0b3I8aW50PiA+IGFkamFjZW5jeV9saXN0OwoKCQlpbnQgcGFyZW50W3ZlcnRpY2VzICsgMV07CgkJLy8gRWFjaCBlbGVtZW50IG9mIFBhcmVudCBBcnJheSBob2xkcyB0aGUgTm9kZSB2YWx1ZSBvZiBpdHMgcGFyZW50CgkJaW50IGxldmVsW3ZlcnRpY2VzICsgMV07CgkJLy8gRWFjaCBlbGVtZW50IG9mIExldmVsIEFycmF5IGhvbGRzIHRoZSBMZXZlbCB2YWx1ZSBvZiB0aGF0IG5vZGUKCgkJLy8gSW5pdGlhbGlzaW5nIG91ciBhcnJheXMKCQlmb3IgKGkgPSAwOyBpIDw9IHZlcnRpY2VzOyArK2kpIHsKCQkJbGlzdFtpXSA9IE5VTEw7CgkJCXBhcmVudFtpXSA9IDA7CgkJCWxldmVsW2ldID0gLTE7CgkJfQoKCQkvLyBBZGQgbm9ybWFsIGVkZ2VzIHJlcHJlc2VudGluZyBtb3ZlbWVudHMgYnkgZGljZQoJCWZvciAoaSA9IDE7IGkgPD0gdmVydGljZXM7ICsraSkgewoJCQlmb3IgKGogPSAxOyBqIDw9IDYgJiYgaiArIGkgPD0gMTAwOyArK2opIHsKCQkJCWxpc3RbaV0gPSBhZGRFZGdlKGxpc3RbaV0sIGkgKyBqKTsKCQkJCSsrZWRnZXM7CgkJCX0KCQl9CgoJCWludCBudW1MYWRkZXJzLCBudW1TbmFrZXM7CgkJY2hhciB0ZW1wOwoKCQlzY2FuZigiJWQiLCAmbnVtTGFkZGVycyk7CgoJCS8vIExhZGRlciBFZGdlcwoJCWludCBsYWRkZXJzW251bUxhZGRlcnNdWzJdOwoKCQlmb3IgKGkgPSAwOyBpIDwgbnVtTGFkZGVyczsgKytpKSB7CgkJCXNjYW5mKCIlZCVjJWQiLCAmbGFkZGVyc1tpXVswXSwgJnRlbXAsICZsYWRkZXJzW2ldWzFdKTsKCgkJCWogPSBsYWRkZXJzW2ldWzBdIC0gNjsKCgkJCWlmIChqIDwgMSkgewoJCQkJaiA9IDE7CgkJCX0KCgkJCWZvciAoOyBqIDwgbGFkZGVyc1tpXVswXTsgKytqKSB7CgkJCQlyZXBsYWNlKGxpc3Rbal0sIGxhZGRlcnNbaV1bMF0sIGxhZGRlcnNbaV1bMV0pOwoJCQl9CgkJfQoKCQlzY2FuZigiJWQiLCAmbnVtU25ha2VzKTsKCgkJLy8gU25ha2VzIEVkZ2VzCgkJaW50IHNuYWtlc1tudW1TbmFrZXNdWzJdOwoKCQlmb3IgKGkgPSAwOyBpIDwgbnVtU25ha2VzOyArK2kpIHsKCQkJc2NhbmYoIiVkJWMlZCIsICZzbmFrZXNbaV1bMF0sICZ0ZW1wLCAmc25ha2VzW2ldWzFdKTsKCgkJCWogPSBzbmFrZXNbaV1bMF0gLSA2OwoKCQkJaWYgKGogPCAwKSB7CgkJCQlqID0gMDsKCQkJfQoKCQkJZm9yICg7IGogPCBzbmFrZXNbaV1bMF07ICsraikgewoJCQkJcmVwbGFjZShsaXN0W2pdLCBzbmFrZXNbaV1bMF0sIHNuYWtlc1tpXVsxXSk7CgkJCX0KCQl9CgoJCWJyZWFkdGhGaXJzdFNlYXJjaChsaXN0LCB2ZXJ0aWNlcywgcGFyZW50LCBsZXZlbCk7CgkJcHJpbnRmKCIlZFxuIiwgbGV2ZWxbdmVydGljZXNdKTsKCQlwcmludFNob3J0ZXN0UGF0aChwYXJlbnQsIDEwMCwgMSk7CgkJcHJpbnRmKCJcbiIpOwoJfQoKCXJldHVybiAwOwp9