poj 3984 迷宫问题(BFS+输出路径)

简介: poj 3984 迷宫问题(BFS+输出路径)



迷宫问题

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 11323   Accepted: 6776

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)

Source


题目分析:

此题的移动方向已经很明确要么下要么右







<span style="font-size:24px;">#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int mark[7][7],map[7][7];
struct node
{
    int a;
    int b;
};
stack<node> q;
void bfs(int x,int y)
{
    
    if(!mark[x][y])
    {
        node arr;
        arr.a=x;
        arr.b=y;
        mark[x][y]=1;
        q.push(arr);
    }
    if(x==5&&y==5)  return ;
    if(!mark[x+1][y]&&!map[x+1][y]) bfs(x+1,y);
    else if(!mark[x][y+1]&&!map[x][y+1]) bfs(x,y+1);
    else 
    {
        node arr;
        q.pop();
        arr=q.top();
        bfs(arr.a,arr.b);
    }
}
int main()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            //cin>>map[i][j];
            scanf("%d",&map[i][j]);
    memset(mark,0,sizeof(mark));
    for(int i=0;i<7;i++)
    {
        map[0][i]=1;
        map[i][0]=1;
        map[i][6]=1;
        map[6][i]=1;    
    }
    bfs(1,1);
    vector<node> v;
    while(!q.empty())
    {
        v.push_back(q.top());
        q.pop();
    }  
    for(int i=v.size()-1;i>=0;i--)
        printf("(%d, %d)\n",v[i].a-1,v[i].b-1);
 return 0;   
}</span>






目录
相关文章
|
6月前
|
存储 算法
使用 BFS 解决走迷宫问题
使用 BFS 解决走迷宫问题
77 1
|
6月前
|
算法 Java C++
走迷宫(BFS)
走迷宫(BFS)
44 0
|
算法 C语言 C++
【动态规划】不同路径,编辑距离题解及代码实现
两题由简单到难得DP问题!助我们拿下DP!
65 0
每日三题-最大子数组和、不同路径、最小路径和
每日三题-最大子数组和、不同路径、最小路径和
72 0
每日三题-最大子数组和、不同路径、最小路径和
|
存储
【每日一题Day61】寻找图中是否存在路径 | BFS 并查集
初始时将source设为已访问,并且将其加入队列。之后每次将队列中的节点出队,并将其能够到达的未访问过的节点入队。如果访问到destination,则直接返回true;如果队列为空,仍未访问到destination,则返回false
115 0
AcWing 周赛13 3813. 最大路径权值(拓扑排序 DAG上dp)
AcWing 周赛13 3813. 最大路径权值(拓扑排序 DAG上dp)
112 0
|
存储 定位技术 C++
【31. 走迷宫(BFS)】
## 思路 - 用 `g[n][m] `存储地图,`d[n][m]` 存储起点到 n,m 的距离。 - 从起点开始广度优先遍历地图。 - 当地图遍历完,就求出了起点到各个点的距离,输出`d[n][m]`即可。
292 0
【31. 走迷宫(BFS)】
|
定位技术
深搜dfs 解决全排列,地图搜索最短距离
深搜dfs 解决全排列,地图搜索最短距离
|
边缘计算
Leetcode --- 岛屿问题(DFS求解)
Leetcode --- 岛屿问题(DFS求解)
Leetcode --- 岛屿问题(DFS求解)