HDU 1026 Ignatius and the Princess I 迷宫范围内的搜索剪枝问题

HDU 1026 Ignatius and the Princess I 迷宫范围内的搜索剪枝问题

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

这个问题是一个典型的类型的问题迷宫广泛的搜索

在网上看到了很多解决方案。

没什么解决问题的分析报告,不指出其中的关键点。代码更像是一大抄。一些分析师也有很大的文章分析。只是不要全部命中关键,什么是广泛而深刻的,甚至搜索发现,在分析差异。为什么快速搜索宽像,什么样的风暴喊搜索,都错了。代码都是抄过的。

通过一大段的时间研究,最终搞通了。

本题尽管能够说是广搜。可是当中的关键却是剪枝法。为什么呢?

由于迷宫并不能简单地广搜就能搜索出全部路径的,甚至仅仅要迷宫大点就不能搜索出是否有路径。假设没有条件剪枝的情况下。不信,你严格写一个广搜搜索一下迷宫路径看看。当然你写了个错误的广搜。自然得出错误的答案了。

常见的错误是一格一格地扩展迷宫就以为是迷宫的广搜了,错!

真正的广搜是须要把迷宫建图。然后广搜。

事实上真正的关键是剪枝:

剪枝思考就是要思考什么时候应该扩展到下一格?是否合法的格子就一定能够扩展?当然不是,是须要依据题意剪枝。本题的题意是求用时最小的路径。故此能够由此想到应该是以时间比較来决定是否须要扩展到下一格的。

即下一格有可能找到更加优的解就扩展。否则就不扩展。

这样一剪枝之后。就能够使用所谓的广搜了。

那么为什么本题。或者能够说本题题型的题目不能够使用深搜呢?

由于上面的剪枝条件是每一层去剪枝的,假设使用深搜,那么这种剪枝条件就无法用上了。

另一种做法就是利用优先队列。优先扩展当前最小用时的格子。那么就能够不用反复搜索下一格了。这也是利用了上面的剪枝思想。

只是仅仅要理解了上面的关键剪枝点,那么这种题目都能够随心所欲地攻克了。

至于本题的记录路径就是编程功底的測试了,不用说什么思路了。不会的仅仅能说编码能力不行了。

或许也有不懂分析的人也把代码敲对了,或许是他运气不错。或许是他真的是天才级的人物!

反正几率都非常低,最大几率还是他的代码是抄来的。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

/*
关键理解:仅仅有当下一个格子更新了最小值的时候才须要扩展到这个格子。否则就不须要扩展到这个格子。这个也是相当于广搜的剪枝点。

理解不了这点的。就没有透切理解这个问题。*/namespace IgnatiusandthePrincessI1026{const int MAX_N = 101;char Maze[MAX_N][MAX_N];int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};struct Node{ int sec, x, y; Node *p;};Node mazeRec[MAX_N][MAX_N];int N, M;inline bool isLegal(int r, int c){ return 0<=r && 0<=c && r<N && c<M && Maze[r][c] != 'X';}inline int getSec(int r, int c){ if (Maze[r][c] == '.') return 1; return Maze[r][c] - '0' + 1;}void getPath(){ for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { mazeRec[i][j].sec = INT_MAX; mazeRec[i][j].x = i, mazeRec[i][j].y = j; mazeRec[i][j].p = NULL; } } queue<Node *> qu; Node *p = &mazeRec[N-1][M-1]; //注意计算错误:p->sec = Maze[N-1][M-1] or = getSec(N-1, M-1) p->sec = getSec(N-1, M-1)-1;//终点也可能是有敌人,起点规定了无敌人 qu.push(p); while (!qu.empty()) { p = qu.front(); qu.pop(); for (int i = 0; i < 4; i++) { int tx = p->x + dx[i], ty = p->y + dy[i]; if (!isLegal(tx, ty)) continue; int sec = getSec(tx, ty); Node *tmp = &mazeRec[tx][ty]; if (p->sec+sec < tmp->sec) { tmp->sec = p->sec+sec; tmp->p = p; qu.push(tmp); } /*关键理解:仅仅有当下一个格子更新了最小值的时候才须要扩展到这个格子。否则就不须要扩展到这个格子。这个也是相当于广搜的剪枝点。

理解不了这点的,就没有透切理解这个问题。*//*各种错误教训! qu.push(tmp); tmp.vis = true; //错误多个else。逻辑错误else tmp->vis = true //Maze[tx][ty] = 'X'; tmp.sec = p.sec+sec; tmp.p = &mazeRec[p.x][p.y]; //错误:tmp->p = p; //错误:tmp->sec = min(tmp->sec, p->sec+sec);*/ } }}int main(){ while (~scanf("%d %d", &N, &M)) { while (getchar() != '\n'); for (int i = 0; i < N; i++) { gets(Maze[i]); } getPath(); Node *p = &mazeRec[0][0]; if (p->sec == INT_MAX) puts("God please help our poor hero."); else { printf("It takes %d seconds to reach the target position, let me show you the way.\n", p->sec); int s = 1; for (; p->p; p = p->p) { int x = p->p->x, y = p->p->y; printf("%ds:(%d,%d)->(%d,%d)\n", s++, p->x, p->y, x, y); if (Maze[x][y] == '.') continue; int fig = Maze[x][y] - '0';//错误少-'0' for (int i = 0; i < fig; i++) { printf("%ds:FIGHT AT (%d,%d)\n", s++, x, y); } } } puts("FINISH"); } return 0;}

版权声明:笔者靖心脏。景空间地址:http://blog.csdn.net/kenden23/。只有经过作者同意转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117152.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • grep 命令详解_grep命令详解

    grep 命令详解_grep命令详解一:grep命令的基本概念和用途grep命令是linux中一种强大的文本搜索工具,它能使用正则表达式搜索文本,并把匹配的行打印出来。在一个或多个文件中搜素字符串模式,如果字符串模式包括空格,也必须被引用,模式后的所有字符串被看作文件名。搜索的结果被送到标准输出(stdout),不影响原文件内容。grep也可以用于shell脚本,因为grep通过返回一个状态值来说明搜索的结果,如果模式搜索成功,则返回0;如果搜索不成功,则返回1;如果搜索的文件不存在,则返回2;我们利用这些返回值就可以进行一些自动化的文

  • 深度学习中的9种归一化方法概述

    深度学习中的9种归一化方法概述9种归一化(Normalization)方法概述

    2022年10月28日
  • Javadb学习 连接Javadb的两种方法 javadb-10_5_1_1.zip[通俗易懂]

    Javadb学习 连接Javadb的两种方法 javadb-10_5_1_1.zip[通俗易懂]Javadb学习环境变量设置:DERBY_HOME=D:\ProgramFiles\Environment\javadbpath=.;%JAVA_HOME%/bin;%path%;%CATALINA_HOME%/bin;%ANT_HOME%/bin;%ANT_HOME%/bin;C:\ProgramFiles\IDMComputerSolutions\UltraEdit\;%JA…

  • 2022计算机Java二级考试四十五套题真题【收藏版】(一周裸考计划)[通俗易懂]

    当你看到这篇文章的时候,相信自己已经在考试的路上,或者即将踏入计算机二级考试的道路。先收藏为敬。再网上看了很多的java面试题,有很多都是零零碎碎的,有或者是需要付费加密????的,加个vip什么的,故而以下是博主整理的有关java面试题的以下内容,我想以一种幽默风趣????的风格来给大家分享和探讨。另外附加有一些公司的面试真题(内部分享)下面我就开启????耳机模式。并且⭐是重要部分,要记易考噢。

  • Python+Selenium面试题(附详细解答)

    Python+Selenium面试题(附详细解答)一、选择题(1分18题,共18分)1.下面哪些关于自动化测试的说法是错误的:(ACD)A.自动化测试可以完全取代手工测试B.自动化测试可以大幅度减少测试团队的工作量C.性能测试不能自动化D.自动化测试能够发现大量的新缺陷2.下列哪种是Python元组的定义方式?(ABCD)A.([2,3],1) B.(1,) C.(1,{“name”:”sex”}) D….

  • Java基础语法(七)条件控制语句的骚操作

    Java基础语法(七)条件控制语句的骚操作

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号