#include <stdio.h><\/p>\n
\tstruct point {
\n\t int row;
\n\t int col;
\n\t};<\/p>\n
\t\/* define point stack *\/
\n\tstruct point stack[512];<\/p>\n
\t\/* define stack pointer *\/
\n\tint top = 0;<\/p>\n
\t\/* define push() *\/
\n\tvoid push(struct point node)
\n\t{
\n\t stack[top++] = node;
\n\t return;
\n\t}<\/p>\n
\t\/* define pop() *\/
\n\tstruct point pop(void)
\n\t{
\n\t return stack[–top];
\n\t}<\/p>\n
\t\/* define isempty() *\/
\n\tint isempty(void)
\n\t{
\n\t return (top == 0);
\n\t}<\/p>\n
\tint maze[5][5] =
\n\t{
\n\t { 0, 0, 0, 0, 0 },
\n\t { 1, 1, 1, 1, 0 },
\n\t { 0, 0, 0, 1, 0 },
\n\t { 0, 0, 0, 1, 0 },
\n\t { 0, 0, 0, 1, 0 }
\n\t};<\/p>\n
\tstruct point father[5][5] =
\n\t{
\n\t {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
\n\t {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
\n\t {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
\n\t {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
\n\t {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1} },
\n\t};<\/p>\n
\tvoid print_stack(void)
\n\t{
\n\t int i;<\/p>\n
\t for (i = top-1; i >= 0; i–)
\n\t printf("(%d, %d) n", stack[i].row, stack[i].col);<\/p>\n
\t printf("————————n");<\/p>\n
\t return;
\n\t}<\/p>\n
\tvoid print_maze(void)
\n\t{
\n\t int i, j;<\/p>\n
\t for (i = 0; i < 5; i++)
\n\t {
\n\t for (j = 0; j < 5; j++)
\n\t {
\n\t printf("%d ", maze[i][j]);
\n\t }
\n\t printf("n");
\n\t }<\/p>\n
\t printf("————————n");
\n\t return;
\n\t}<\/p>\n
\tvoid print_father(void)
\n\t{
\n\t int i, j;
\n\t struct point node;<\/p>\n
\t for (i = 0; i < 5; i++)
\n\t {
\n\t for (j = 0; j < 5; j++)
\n\t {
\n\t node = father[i][j];
\n\t printf("(%2d,%2d) ", node.row, node.col);
\n\t }
\n\t printf("n");
\n\t }<\/p>\n
\t printf("————————n");
\n\t return;
\n\t}<\/p>\n
\tstruct point entry = {0, 0};
\n\tstruct point out = {4, 4};<\/p>\n
\tvoid backtrack(struct point p)
\n\t{
\n\t \/* define tmp node = curr point *\/
\n\t struct point node = p;
\n\t struct point null = {-1, -1};
\n\t struct point top, topfather;
\n\t int row, col;<\/p>\n
\t#ifdef DEBUG
\n\t printf("backtrack is begin n");
\n\t print_stack();
\n\t getchar();
\n\t#endif<\/p>\n
\t \/* peak stack top *\/
\n\t top = pop();
\n\t push(top);<\/p>\n
\t \/* get top father *\/
\n\t topfather = father[top.row][top.col];<\/p>\n
\t while(1)
\n\t {
\n\t \/* get curr node's row & col *\/
\n\t row = node.row;
\n\t col = node.col;<\/p>\n
\t \/* clear maze[][] = 0 *\/
\n\t maze[row][col] = 0;<\/p>\n
\t \/* get current node's father *\/
\n\t node = father[row][col];<\/p>\n
\t \/* clear father[][] = (-1,-1) *\/
\n\t father[row][col] = null;
\n\t#ifdef DEBUG
\n\t print_maze();
\n\t print_father();
\n\t getchar();
\n\t#endif<\/p>\n
\t \/* end condition *\/
\n\t \/* peak stack top point -> topfather *\/
\n\t \/* if node == topfather, break *\/
\n\t if (node.row == topfather.row && node.col == topfather.col)
\n\t break;
\n\t }<\/p>\n
\t\/\/ printf("backtrack is over n");
\n\t}<\/p>\n
\tvoid print_solution(void)
\n\t{
\n\t \/* define tmp node = exit point *\/
\n\t struct point node = out;
\n\t int row, col;
\n\t static int counter = 0;<\/p>\n
\t while(1)
\n\t {
\n\t \/* print curr node *\/
\n\t printf("(%d, %d) <- ", node.row, node.col);
\n\t row = node.row;
\n\t col = node.col;<\/p>\n
\t \/* get current node's father *\/
\n\t node = father[row][col];<\/p>\n
\t \/* if current node is (-1,-1), then break *\/
\n\t if (node.row == -1)
\n\t break;
\n\t }<\/p>\n
\t printf("n");
\n\t printf("%d solution is over n", ++counter); <\/p>\n
\t return;
\n\t}<\/p>\n
\tint main(void)
\n\t{
\n\t \/\/struct point entry = {2, 2};
\n\t struct point curr;
\n\t struct point node;
\n\t int flag = 0;<\/p>\n
\t printf("hello, mazer!n");<\/p>\n
\t \/* init stack, push entry point *\/
\n\t push(entry);<\/p>\n
\t#ifdef DEBUG
\n\t print_stack();
\n\t print_maze();
\n\t print_father();
\n\t#endif<\/p>\n
\t while (!isempty())
\n\t {
\n\t \/* get the stack top *\/
\n\t curr = pop();
\n\t
\n\t \/* flag curr point *\/
\n\t maze[curr.row][curr.col] = 2;<\/p>\n
\t \/* check it *\/
\n\t \/\/ print_stack();
\n\t \/\/ print_maze();<\/p>\n
\t \/* judgement if curr is exit point *\/
\n\t if (curr.row == out.row && curr.col == out.col)
\n\t {
\n\t printf("one solution found! n");
\n\t print_solution();<\/p>\n
\t \/* begin to backtrack *\/
\n\t backtrack(curr);
\n\t \/\/ break;
\n\t continue;
\n\t }<\/p>\n
\t \/* expand from curr *\/
\n\t flag = 0;<\/p>\n
\t \/* look left *\/
\n\t if (curr.col-1 >= 0 && maze[curr.row][curr.col-1] == 0)
\n\t {
\n\t \/* push left point *\/
\n\t node.row = curr.row;
\n\t node.col = curr.col – 1;
\n\t \/* node 's father is null *\/
\n\t if (father[node.row][node.col].row == -1)
\n\t {
\n\t push(node);
\n\t \/* remember father *\/
\n\t father[node.row][node.col] = curr;
\n\t flag++;
\n\t }
\n\t }<\/p>\n
\t \/* look up *\/
\n\t if (curr.row-1 >= 0 && maze[curr.row-1][curr.col] == 0)
\n\t {
\n\t \/* push up point *\/
\n\t node.row = curr.row – 1;
\n\t node.col = curr.col;
\n\t if (father[node.row][node.col].row == -1)
\n\t {
\n\t push(node);
\n\t \/* remember father *\/
\n\t father[node.row][node.col] = curr;
\n\t flag++;
\n\t }
\n\t }<\/p>\n
\t \/* look right *\/
\n\t if (curr.col+1 < 5 && maze[curr.row][curr.col+1] == 0)
\n\t {
\n\t \/* push right point *\/
\n\t node.row = curr.row;
\n\t node.col = curr.col + 1;
\n\t if (father[node.row][node.col].row == -1)
\n\t {
\n\t push(node);
\n\t \/* remember father *\/
\n\t father[node.row][node.col] = curr;
\n\t flag++;
\n\t }
\n\t }<\/p>\n
\t \/* look down *\/
\n\t if (curr.row+1 < 5 && maze[curr.row+1][curr.col] == 0)
\n\t {
\n\t \/* push down point *\/
\n\t node.row = curr.row + 1;
\n\t node.col = curr.col;
\n\t if (father[node.row][node.col].row == -1)
\n\t {
\n\t push(node);
\n\t \/* remember father *\/
\n\t father[node.row][node.col] = curr;
\n\t flag++;
\n\t }
\n\t }
\n\t#ifdef DEBUG
\n\t print_stack();
\n\t print_father();
\n\t getchar();
\n\t#endif<\/p>\n
\t \/* if no way out (curr node has no expand node) *\/
\n\t if (flag == 0)
\n\t backtrack(curr);
\n\t }<\/p>\n
\t printf("maze is over n");
\n\t\/\/ print_stack();
\n\t
\n\t return 0;
\n\t}
\n\t <\/p>\n","protected":false},"excerpt":{"rendered":"
#include <stdio.h> struct point { &nb […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-758","post","type-post","status-publish","format-standard","hentry","category-linux-c"],"_links":{"self":[{"href":"https:\/\/www.kumouse.com\/index.php?rest_route=\/wp\/v2\/posts\/758","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kumouse.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kumouse.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kumouse.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kumouse.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=758"}],"version-history":[{"count":0,"href":"https:\/\/www.kumouse.com\/index.php?rest_route=\/wp\/v2\/posts\/758\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.kumouse.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=758"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kumouse.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=758"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kumouse.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=758"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}