热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

POJ3083:糖果children的DFS和BFS算法探索

题目链接:http://poj.org/problem?id=3083。题目描述:给定一个迷宫,其中'S'表示起点,'E'表示终点,'#'表示墙壁,'.'表示可通行的道路。起点和终点均位于迷宫的边界上,并且保证存在唯一路径。任务是求从起点'S'到终点'E'的最短路径步数,且优先考虑向左转弯。通过深度优先搜索(DFS)和广度优先搜索(BFS)算法进行路径探索,分析两种方法的优劣及适用场景。

题目链接:http://poj.org/problem?id=3083

题目大意:给你一个迷宫,S是起点,E是终点,#是墙,.是路,S、E在迷宫的边界,并且有唯一解;求优先左转S到E的步数,优先右转S到E的步数,以及S到E的最短步数。

题解:

1、本题的难点在于左转优先以及右转优先,下一步的方向取决于当前位置的方向,用DFS不断的按优先方向遍历一遍迷宫即可;我定义如图:

  前(0)  
左(1) 当前位置方向(dir) 右(3)
  后(2)  

以左转优先为例,便利迷宫的方向依次为:左、前、右、后;即:

左:(dir+1)%4

前;(dir+0)%4

右:(dir+3)%4

后:(dir+2)%4

右转优先只要改变一下遍历方向即可;

2、求S到E的最短路用BFS遍历即可;

*具体看代码注释

#include 
#include 
#include 
#include 
using namespace std;

struct point
{
    int x,y,step;
};
char map[50][50];
queueq;
int n,m;
int lstep,rstep;
int go[4][2]={-1,0,0,-1,1,0,0,1};//四个方向,按左、前、右、后存储

int is_way(int x,int y)//判断此点是否可走
{
    if(x<0 || x>=n || y<0 || y>=m || map[x][y]==#)
        return 0;
    return 1;
}

void ldfs(int x,int y,int dir)//左转优先,x,y记录当前位置,dir记录当前方向
{
    lstep++;//步数
    //cout<//getchar();
    if(map[x][y]==E) return;//找到终点退出
    if( is_way(x+go[(dir+1)%4][0],y+go[(dir+1)%4][1]) )//左转
        ldfs( x+go[(dir+1)%4][0], y+go[(dir+1)%4][1], (dir+1)%4 );
    else if( is_way(x+go[(dir)%4][0],y+go[(dir)%4][1]) )//前走
        ldfs( x+go[(dir)%4][0], y+go[(dir)%4][1], (dir)%4 );
    else if( is_way(x+go[(dir+3)%4][0],y+go[(dir+3)%4][1]) )//右转
        ldfs( x+go[(dir+3)%4][0], y+go[(dir+3)%4][1], (dir+3)%4 );
    else ldfs( x+go[(dir+2)%4][0], y+go[(dir+2)%4][1], (dir+2)%4 );//后退
}

void rdfs(int x,int y,int dir)//右转优先
{
    rstep++;
    if(map[x][y]==E) return;
    if( is_way(x+go[(dir+3)%4][0],y+go[(dir+3)%4][1]) )//右转
        rdfs( x+go[(dir+3)%4][0], y+go[(dir+3)%4][1], (dir+3)%4 );
    else if( is_way(x+go[(dir)%4][0],y+go[(dir)%4][1]) )//前走
        rdfs( x+go[(dir)%4][0], y+go[(dir)%4][1], (dir)%4 );
    else if( is_way(x+go[(dir+1)%4][0],y+go[(dir+1)%4][1]) )//左转
        rdfs( x+go[(dir+1)%4][0], y+go[(dir+1)%4][1], (dir+1)%4 );
    else rdfs( x+go[(dir+2)%4][0], y+go[(dir+2)%4][1], (dir+2)%4 );//后退
}

int bfs()//求S到E最短距离,BFS模板即可
{
    while(!q.empty())
    {
        point p=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=p.x+go[i][0];
            int y=p.y+go[i][1];
            if(map[x][y]==E) return p.step+1;
            if(is_way(x,y))
            {
                point temp;
                temp.x=x;
                temp.y=y;
                temp.step=p.step+1;
                q.push(temp);
                map[x][y]=#;
            }
        }
    }
    return 0;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        while(!q.empty())
            q.pop();
        int x,y;
        cin>>m>>n;
        for(int i=0;i)
            for(int j=0;j)
            {
                cin>>map[i][j];
                if(map[i][j]==S)
                {
                    x=i;
                    y=j;
                }
            }
        lstep=0;
        rstep=0;
        ldfs(x,y,0);
        rdfs(x,y,0);
        point p;
        p.x=x;
        p.y=y;
        p.step=1;
        q.push(p);
        map[x][y]=#;
        cout<<<endl;
    }
    return 0;
}

后:(dir+2)%4

POJ 3083 Children of the Candy Corn (DFS+BFS)


推荐阅读
  • 本文介绍了SIP(Session Initiation Protocol,会话发起协议)的基本概念、功能、消息格式及其实现机制。SIP是一种在IP网络上用于建立、管理和终止多媒体通信会话的应用层协议。 ... [详细]
  • importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]
  • 本文详细探讨了BCTF竞赛中窃密木马题目的解题策略,重点分析了该题目在漏洞挖掘与利用方面的技巧。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 回顾两年前春节期间的一个个人项目,该项目原本计划参加竞赛,但最终作为练习项目完成。独自完成了从编码到UI设计的全部工作,尽管代码量不大,但仍有一定的参考价值。本文将详细介绍该项目的背景、功能及技术实现。 ... [详细]
  • 如何在PHP中安装Xdebug扩展
    本文介绍了如何从PECL下载并编译安装Xdebug扩展,以及如何配置PHP和PHPStorm以启用调试功能。 ... [详细]
  • 本文探讨了在一个物理隔离的环境中构建数据交换平台所面临的挑战,包括但不限于数据加密、传输监控及确保文件交换的安全性和可靠性。同时,作者结合自身项目经验,分享了项目规划、实施过程中的关键决策及其背后的思考。 ... [详细]
  • 心理学经典:《思考致富》
    《思考致富》是由美国著名成功学大师拿破仑·希尔撰写的一部重要著作,该书基于希尔长达20年的深入研究和访谈,探讨了个人成功的核心要素。书中不仅揭示了成功的关键,还提供了一系列实用的方法和策略。 ... [详细]
  • empty,isset首先都会检查变量是否存在,然后对变量值进行检测。而is_null只是直接检查变量值,是否为null,因此如果变量未定义就会出现错误!检测一个变量是否是null ... [详细]
  • 在处理大数据量的SQL分页查询时,通常需要执行两次查询来分别获取数据和总记录数。本文介绍了一种优化方法,通过单次查询同时返回分页数据和总记录数,从而提高查询效率。 ... [详细]
  • 在日常生活中,支付宝已成为不可或缺的支付工具之一。本文将详细介绍如何通过支付宝实现免费提现,帮助用户更好地管理个人财务,避免不必要的手续费支出。 ... [详细]
  • 我的读书清单(持续更新)201705311.《一千零一夜》2006(四五年级)2.《中华上下五千年》2008(初一)3.《鲁滨孙漂流记》2008(初二)4.《钢铁是怎样炼成的》20 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 嵌套列表的扁平化处理
    本文介绍了一种方法,用于遍历嵌套列表中的每个元素。如果元素是整数,则将其添加到结果数组中;如果元素是一个列表,则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]
author-avatar
viggieg-may_789
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有