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>






目录
相关文章
|
算法 C语言 C++
【动态规划】不同路径,编辑距离题解及代码实现
两题由简单到难得DP问题!助我们拿下DP!
60 0
|
机器学习/深度学习 定位技术
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1
125 1
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
每日三题-最大子数组和、不同路径、最小路径和
每日三题-最大子数组和、不同路径、最小路径和
68 0
每日三题-最大子数组和、不同路径、最小路径和
|
存储
【每日一题Day61】寻找图中是否存在路径 | BFS 并查集
初始时将source设为已访问,并且将其加入队列。之后每次将队列中的节点出队,并将其能够到达的未访问过的节点入队。如果访问到destination,则直接返回true;如果队列为空,仍未访问到destination,则返回false
115 0
AcWing 周赛13 3813. 最大路径权值(拓扑排序 DAG上dp)
AcWing 周赛13 3813. 最大路径权值(拓扑排序 DAG上dp)
110 0
|
测试技术
输出全排列 (20 分)(dfs模板题)
输出全排列 (20 分)(dfs模板题)
106 0
|
定位技术
深搜dfs 解决全排列,地图搜索最短距离
深搜dfs 解决全排列,地图搜索最短距离
|
索引
【LeetCode剑指offer12】矩阵中的路径(dfs回溯)
递归参数: 当前字符在矩阵 grid 中的行索引 i 和列索引 j ,当前目标字符(匹配的)在目标字符串 word 中的索引 k 。
117 0
【LeetCode剑指offer12】矩阵中的路径(dfs回溯)
|
机器学习/深度学习 算法
搜索算法dfs和bfs解析(附有例题)
搜索算法dfs和bfs解析(附有例题)
204 0
搜索算法dfs和bfs解析(附有例题)