欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3984 迷宫问题(广搜)

程序员文章站 2022-05-20 22:52:15
...

【题目链接】
http://poj.org/problem?id=3984

题目意思

给个5*5的地图,1墙,0可以走,问你从左上到右下最少步数怎么走输出路径

解题思路

简单的广搜,每次只要控制左和下,设个前驱数组存路径就可以了。

代码部分


#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <string>
#include <map>
using namespace std;
#define LL long long
#define inf 0x3f3f3f3
const int N = 1e5+5;
struct node
{
    int x,y,step;
}s;
node pre[10][10];
int maps[10][10];
int vis[10][10];
int dir[2][2]={1,0,0,1};
void dfs (int x, int y)
{
    if (x==0 && y== 0)
    {
        printf("(%d, %d)\n",x,y);
        return;
    }
    node t = pre[x][y];
    dfs(t.x,t.y); 
    printf("(%d, %d)\n",x,y);
}
void bfs ()
{
    queue <node>q;
    q.push(s);
    vis[0][0] = 1;
    while (!q.empty())
    {
        node t,tt;
        t = q.front();
        q.pop();
        tt.step = t.step+1;
        for (int i = 0; i < 2; i++)
        {
            tt.x = t.x+dir[i][0];
            tt.y = t.y+dir[i][1];
            pre[tt.x][tt.y] = t;
            if (tt.x == 4 && tt.y ==4)
                return;
            if (tt.x < 5 && tt.y <5 && !vis[tt.x][tt.y] && !maps[tt.x][tt.y])
            {
                vis[tt.x][tt.y] = 1;
                q.push(tt);
            }
        }
    }
}
int main()
{
    memset(vis,0,sizeof (vis));
    for (int i =0; i < 5; i++)
        for (int j = 0; j < 5;j++)
            cin>>maps[i][j];
    s.x = 0;
    s.y = 0;
    s.step = 0;
    bfs();
    dfs(4,4);
    return 0;
}