热门标签 | 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)


推荐阅读
  • 在BZOJ 2563中,阿狸与桃子进行了一场策略博弈游戏。该问题的时间限制为3秒,内存限制为128MB,目前已有97次提交记录。通过对游戏规则和策略的深入分析,本文探讨了双方在不同情况下的最优决策路径,并提出了高效的算法解决方案。 ... [详细]
  • 在基于.NET框架的分层架构实践中,为了实现各层之间的松散耦合,本文详细探讨了依赖注入(DI)和控制反转(IoC)容器的设计与实现。通过合理的依赖管理和对象创建,确保了各层之间的单向调用关系,从而提高了系统的可维护性和扩展性。此外,文章还介绍了几种常见的IoC容器实现方式及其应用场景,为开发者提供了实用的参考。 ... [详细]
  • 在Python编程中,探讨了并发与并行的概念及其区别。并发指的是系统同时处理多个任务的能力,而并行则指在同一时间点上并行执行多个任务。文章详细解析了阻塞与非阻塞操作、同步与异步编程模型,以及IO多路复用技术的应用。通过模拟socket发送HTTP请求的过程,展示了如何创建连接、发送数据和接收响应,并强调了默认情况下socket的阻塞特性。此外,还介绍了如何利用这些技术优化网络通信性能和提高程序效率。 ... [详细]
  • C++ STL 常见函数应用详解与实例解析
    本文详细解析了 C++ STL 中常见函数的应用,并通过具体实例进行说明。特别地,文章对迭代器(iterator)的概念进行了深入探讨,将其视为一种将迭代操作抽象化的工具,便于在不同容器间进行元素访问和操作。此外,还介绍了迭代器的基本类型、使用方法及其在算法中的应用,为读者提供了丰富的实践指导。 ... [详细]
  • 本文深入探讨了ASP.NET中ViewState、Cookie和Session三种状态管理技术的区别与应用场景。ViewState主要用于保存页面控件的状态信息,确保在多次往返服务器过程中数据的一致性;Cookie则存储在客户端,适用于保存少量用户偏好设置等非敏感信息;而Session则在服务器端存储数据,适合处理需要跨页面保持的数据。文章详细分析了这三种技术的工作原理及其优缺点,并提供了实际应用中的最佳实践建议。 ... [详细]
  • 高效批量文件重命名软件
    开发了一款基于Python的高效批量文件重命名软件,并集成了wxWidgets图形用户界面,使用cxfreeze将其打包为独立的可执行文件(exe)。该工具适用于需要频繁处理大量文件的用户,能够显著提高文件管理效率。详细使用说明包含在软件压缩包内。开发环境为Python 2.7和wxWidgets 3.0,运行环境要求兼容Windows系统。 ... [详细]
  • Git基础操作指南:掌握必备技能
    掌握 Git 基础操作是每个开发者必备的技能。本文详细介绍了 Git 的基本命令和使用方法,包括初始化仓库、配置用户信息、添加文件、提交更改以及查看版本历史等关键步骤。通过这些操作,读者可以快速上手并高效管理代码版本。例如,使用 `git config --global user.name` 和 `git config --global user.email` 来设置全局用户名和邮箱,确保每次提交时都能正确标识提交者信息。 ... [详细]
  • 深入解析 OpenCV 2 中 Mat 对象的类型、深度与步长属性
    在OpenCV 2中,`Mat`类作为核心组件,对于图像处理至关重要。本文将深入探讨`Mat`对象的类型、深度与步长属性,这些属性是理解和优化图像操作的基础。通过具体示例,我们将展示如何利用这些属性实现高效的图像缩小功能。此外,还将讨论这些属性在实际应用中的重要性和常见误区,帮助读者更好地掌握`Mat`类的使用方法。 ... [详细]
  • 本文深入探讨了 iOS 开发中 `int`、`NSInteger`、`NSUInteger` 和 `NSNumber` 的应用与区别。首先,我们将详细介绍 `NSNumber` 类型,该类用于封装基本数据类型,如整数、浮点数等,使其能够在 Objective-C 的集合类中使用。通过分析这些类型的特性和应用场景,帮助开发者更好地理解和选择合适的数据类型,提高代码的健壮性和可维护性。苹果官方文档提供了更多详细信息,可供进一步参考。 ... [详细]
  • 本研究提出了一种方法,用于判断两个数组中的元素是否相同,而不考虑其顺序。该方法通过检查数组中每个元素的出现次数来实现。具体实现如下:首先验证输入参数是否为数组,然后对两个数组进行排序并逐个比较元素。若所有元素均相等,则返回 `true`,否则返回 `false`。此方法适用于需要忽略顺序的数组比较场景。 ... [详细]
  • 本文深入解析了线程事件机制的原理及其在实际应用中的案例。通过具体示例,展示了多个线程在不同状态下的交互过程,如线程1、2、3处于等待连接状态,而线程4则负责检测服务的运行状况,并在检测完成后通知其他线程开始连接。该机制有效提高了多线程环境下的资源利用效率和系统响应速度。 ... [详细]
  • 为了在Fragment中直接调用Activity的方法,可以通过定义一个接口并让Activity实现该接口来实现。具体步骤包括:首先在Fragment中声明一个接口,并在Activity中实现该接口。接着,在Fragment中通过类型转换检查Activity是否实现了该接口,如果实现了则调用相应的方法。这种方法不仅提高了代码的解耦性,还增强了模块间的通信效率。此外,还可以通过ViewModel或LiveData等现代Android架构组件进一步优化这一过程,以实现更加高效和可靠的通信机制。 ... [详细]
  • 通过自定义 `TextView`,实现了在用户点击或焦点变化时动态调整字体颜色的效果。该方法利用了 `ColorStateList` 和 `Selector` 资源文件,确保了界面交互的流畅性和视觉效果的提升。具体实现中,通过重写 `onTouchEvent` 和 `onFocusChanged` 方法,精确控制了颜色变化的时机和状态。此外,还对性能进行了优化,确保在高频率操作下依然保持高效响应。 ... [详细]
  • 尽管许多人认为跑步是一项简单的运动,但实际上它涉及诸多专业知识。不正确的跑步方式不仅会降低锻炼效果,还可能引发伤害。例如,穿着不合脚或过于陈旧的跑鞋,会导致足部支撑不足,增加受伤风险。此外,跑步姿势不当、热身不足、过度训练等问题也同样值得关注。本文将详细介绍七大常见跑步误区,并提供专业的改进建议,帮助跑者避免这些问题,提高运动效率和安全性。 ... [详细]
  • 在第六章中,我们将深入探讨MySQL中的多表查询技术,包括联结查询和子查询。联结查询通过将两个或多个表进行连接,基于连接条件生成结果集。常见的联结类型有内联结、外联结和全外联结。交叉联结(CROSS JOIN)虽然使用较少,但其原理是生成所有可能的组合,类似于笛卡尔积的概念。此外,子查询则是在一个查询语句中嵌套另一个查询,用于获取更复杂的数据集。本章将通过实例详细讲解这些查询方法的应用和优化技巧。 ... [详细]
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社区 版权所有