迷宫问题
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 35426 | Accepted: 20088 |
Description
定义一个二维数组:
- int maze[5][5] = {
- 0, 1, 0, 0, 0,
- 0, 1, 0, 1, 0,
- 0, 0, 0, 0, 0,
- 0, 1, 1, 1, 0,
- 0, 0, 0, 1, 0,
- };
它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线.
Input
一个 5 * 5 的二维数组, 表示一个迷宫. 数据保证有唯一解.
Output
左上角到右下角的最短路径, 格式如样例所示.
- Sample Input
- 0 1 0 0 0
- 0 1 0 1 0
- 0 0 0 0 0
- 0 1 1 1 0
- 0 0 0 1 0
- Sample Output
- (0, 0)
- (1, 0)
- (2, 0)
- (2, 1)
- (2, 2)
- (2, 3)
- (2, 4)
- (3, 4)
- (4, 4)
题意: 给出一个迷宫矩阵, 输出一条通路
题解: dfs 找到一条通路, 并用栈记录 (poj 用万能头文件会 CE emmmm)
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- int a[20][20];
- const int n=5;
- stack <pair<int,int>>stk;
- bool dfs(int i,int j) {
- if(i==n-1&&j==n-1) {
- stk.push(make_pair(i,j));
- return true;
- }
- if (i>= 0 && i <= n - 1 && j>= 0 && j <= n - 1) { // 判断边界
- if (a[i][j] == 0) { // 可以走且没走过
- a[i][j] = 1;// 表示走过
- if (dfs(i, j + 1) || dfs(i + 1, j) || dfs(i, j - 1) || dfs(i - 1, j)) { // 接着走
- stk.push(make_pair(i,j));
- return true;
- } else { // 回溯
- a[i][j] = 0;
- return false;
- }
- } else {
- return false;
- }
- } else {
- return false;
- }
- }
- int main() {
- for(int i=0; i<5; i++) {
- for(int j=0; j<5; j++) {
- scanf("%d",&a[i][j]);
- }
- }
- dfs(0,0);
- while(!stk.empty()) {
- printf("(%d, %d)\n",stk.top().first,stk.top().second);
- stk.pop();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2828644.html