本题可以使用BFS和DFS解题,也可以构建图,然后利用Dijsktra解题。
不过因为数据很少,就没必要使用Dijsktra了。
BFS和DFS效率都是一样的,因为都需要搜索所有可能的路径,并记录最短路径和当前路径。
推荐使用DFS,感觉会方便很多,BFS会麻烦很多,因为需要记录并比较路径。
#include <stdio.h> #include <string.h> #include <limits.h> const int MAX_N = 5; const int MAX_RES = MAX_N*MAX_N; int Maze[MAX_N][MAX_N]; int Row[MAX_RES], Col[MAX_RES], resRow[MAX_RES], resCol[MAX_RES], N; const int BLOCK = 1; const int UNBLOCK = 0; inline bool isLegal(int r, int c) { return 0<=r && 0<=c && r<MAX_N && c<MAX_N && Maze[r][c] == 0; } void getPath(int path = 0, int r = 0, int c = 0) { Row[path] = r, Col[path] = c; if (r == MAX_N - 1 && c == MAX_N - 1) { if (path+1 < N) { N = path+1; memcpy(resRow, Row, sizeof(int)*N); memcpy(resCol, Col, sizeof(int)*N); } return ; } Maze[r][c] = BLOCK; if (isLegal(r, c+1)) getPath(path+1, r, c+1); if (isLegal(r+1, c)) getPath(path+1, r+1, c); if (isLegal(r, c-1)) getPath(path+1, r, c-1); if (isLegal(r-1, c)) getPath(path+1, r-1, c); Maze[r][c] = UNBLOCK; } int main() { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { scanf("%d", Maze[i]+j); } } N = INT_MAX; getPath(); if (N != INT_MAX) { for (int i = 0; i < N; i++) { printf("(%d, %d)\n", resRow[i], resCol[i]); } } return 0; }
POJ 3984 迷宫问题 搜索题解,布布扣,bubuko.com
原文:http://blog.csdn.net/kenden23/article/details/38488101