#include<stdio.h> /* 普通寻路算法 回溯法，近似穷举 找到的路径不一定是最短路径 */ #define MAX_NUMBER_LENGTH 6 void print_path(); /*用矩阵表示地图：其中1表示路，0表示没有路，2表示终点，起始地点为（1,0）*/ static int gPath[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = { {0, 0, 0, 0, 1, 1}, {1, 1, 0, 0, 1, 0}, {0, 1, 1, 1, 1, 0}, {0, 0, 1, 0, 1, 2}, {0, 0, 1, 1, 1, 1}, {0, 0, 1, 1, 1, 0} }; static int gValue[MAX_NUMBER_LENGTH][MAX_NUMBER_LENGTH] = {0}; /* 记录已走过的路 */ /*判断函数，判断当前节点是否合法*/ int check_pos_valid(int x, int y) { /* 节点是否出边界 */ if(x < 0 || x>= MAX_NUMBER_LENGTH || y < 0 || y >= MAX_NUMBER_LENGTH) return 0; /* 当前节点是否存在路 */ if(0 == gPath[x][y]) return 0; /* 当前节点是否已经走过 */ if('#' == gValue[x][y]) return 0; return 1; } /*递归的寻找算法*/ int find_path(int x, int y) { if(check_pos_valid(x,y)) { if(2 == gPath[x][y]) { gValue[x][y] = '#'; return 1; } gValue[x][y] = '#'; if(find_path(x, y-1)) return 1; if(find_path(x-1, y)) return 1; if(find_path(x, y+1)) return 1; if(find_path(x+1, y)) return 1; //走到头，没有路可以走 gValue[x][y] = 0; return 0; } return 0; } /*寻找所有路径*/ void find_path_all(int x, int y) { if(check_pos_valid(x,y)) { if(2 == gPath[x][y]){ gValue[x][y] = '#'; print_path(); gValue[x][y] = 0; } gValue[x][y] = '#'; find_path(x, y-1); find_path(x-1, y); find_path(x, y+1); find_path(x+1, y); gValue[x][y] = 0; } } /*打印路径*/ void print_path() { int outer; int inner; for(outer = 0; outer < MAX_NUMBER_LENGTH; outer++){ for(inner = 0; inner < MAX_NUMBER_LENGTH; inner++){ printf("%c ", gValue[outer][inner]); } printf("\n"); } } int main() { find_path(1,0); print_path(); return 0; }版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230587.html原文链接：https://javaforall.net
