上海网站公司建设,网站描述多个词怎么分隔,室内设计师网站有哪些,湛江购房网一.题干 迷宫有一个入口#xff0c;一个出口。一个人从入口走进迷宫#xff0c;目标是找到出口。阴影部分和迷宫的外框为墙#xff0c;每一步走一格#xff0c;每格有四个可走的方向#xff0c;探索顺序为地图方向#xff1a;南#xff08;下#xff09;、东#xff0…一.题干 迷宫有一个入口一个出口。一个人从入口走进迷宫目标是找到出口。阴影部分和迷宫的外框为墙每一步走一格每格有四个可走的方向探索顺序为地图方向南下、东右、北上、西左。 输入输入迷宫数组。第一行数据表示一个 n*n (n100)的迷宫第二行开始的n行为迷宫数据。 其中0表示路1表示墙起点在左上角 1,1 的位置终点在右下角 n,n 的位置。 输出若有解输出从入口到出口的一条路径否则输出 there is no solution! 例上图所示的迷宫数组 输入 4 4 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 输出1,1 2,1 3,1 3,2 3,3 4,3 4,4
测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 4 4↵0 0 1 0↵0 1 0 1↵0 0 0 0↵0 1 0 0↵以文本方式显示 1,1 2,1 3,1 3,2 3,3 4,3 4,4 ↵1秒64M0测试用例 2以文本方式显示 4 4↵0 0 1 0↵1 0 1 1↵0 0 0 1↵0 1 0 1↵以文本方式显示 There is no solution!↵1秒64M0 二.题目分析 我们知道迷宫问题其实就是连通图的遍历。那么显然地可以使用BFS采用BFS的话有个好处第一条即为最短路径按照出题人的想法应该就是采用BFS。试一下 很好要用DFS没要求最短好好好这么写就是想考一下DFS是吧气急败坏了已经
三,代码如下 使用的递推实现的DFS也可以用递归形式上更为简洁
#include iostream
#include stack
using namespace std;
struct Point
{int col;int row;Point(int r, int c) : row(r), col(c) {}bool operator!(const Point p) const{return this-row ! p.row || this-col ! p.col;}
};
Point getNVnode(bool **mark, Point p, int m, int n)
{if (p.row 1 m !mark[p.row 1][p.col]) // 下return Point(p.row 1, p.col);if (p.col 1 n !mark[p.row][p.col 1]) // 右return Point(p.row, p.col 1);if (p.row - 1 0 !mark[p.row - 1][p.col]) // 上return Point(p.row - 1, p.col);if (p.col - 1 0 !mark[p.row][p.col - 1]) // 左return Point(p.row, p.col - 1);return Point(-1, -1);
}
void DFSpath(void *maze, int m, int n, const Point startP, Point endP, stackPoint pointStack)
{int **maze2d new int *[m];for (int i 0; i m; i)maze2d[i] (int *)maze i * n;bool **mark new bool *[m];for (int i 0; i m; i){mark[i] new bool[n];for (int j 0; j n; j)mark[i][j] *((int *)maze i * n j);}pointStack.push(startP);mark[startP.row][startP.col] true;while (pointStack.empty() false pointStack.top() ! endP){Point NextP getNVnode(mark, pointStack.top(), m, n);if (NextP.row -1){pointStack.pop();continue;}mark[NextP.row][NextP.col] true;pointStack.push(NextP);}
}int main()
{int N;cin N N;if (N 1)printf(1,1 \n);int maze[N][N];for (int i 0; i N; i)for (int j 0; j N; j)cin maze[i][j];Point startP(0, 0);Point endP(N - 1, N - 1);stackPoint pointStack;DFSpath(maze, N, N, startP, endP, pointStack);if (pointStack.empty() true)cout There is no solution! endl;else{stackPoint tmpStack;while (pointStack.empty() false){tmpStack.push(pointStack.top());pointStack.pop();}while (tmpStack.empty() false){couttmpStack.top().row1 tmpStack.top().col1 ;tmpStack.pop();}cout endl;}
}
