当前位置:网站首页>HDU 1026 search pruning problem within the labyrinth of Ignatius and the prince I
HDU 1026 search pruning problem within the labyrinth of Ignatius and the prince I
2022-07-06 19:48:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
This problem is a typical type of problem maze extensive Search for .
I see a lot of solutions on the Internet .
There's no problem-solving analysis , Don't point out the key points . The code is more like a copy . Some analysts also have big articles to analyze . Just don't hit the key all the time , What is broad and profound , Even search and find , Analyzing differences . Why search wide image quickly , What kind of storm calls search , All wrong. . The code is copied .
Through a long period of research , It finally got through .
Although this topic can be said to be extensive search . But the key is pruning . Why? ?
Because the maze can't search all the paths simply by searching widely , Even if the maze is a little bigger, you can't find out whether there is a path . Suppose there is no conditional pruning . Don't believe it , You strictly write a wide search and search the maze path to see . Of course, you wrote a wrong search . Naturally, I got the wrong answer .
The common mistake is to expand the maze one by one, thinking it is a wide search of the maze , wrong !
The real search is to map the maze . Then search widely .
In fact, the real key is pruning :
Pruning thinking is to think about when it should be extended to the next grid ? Whether the lattice is legal or not must be able to expand ? Of course not. , It is necessary to prune according to the meaning of the topic . The meaning of this question is to find the path with the smallest time . Therefore, it can be thought that it should be decided by time comparison whether it needs to be extended to the next grid .
That is, if the next lattice is possible to find a better solution, it will expand . Otherwise, do not expand .
After such a pruning . You can use the so-called wide search .
So why this topic . Or it can be said that the topic of this topic type cannot use deep search ?
Because the above pruning condition is that each layer is pruned , Suppose you use deep search , Then this pruning condition cannot be used .
Another way is to use priority queues . Give priority to expanding the lattice with the current minimum time . Then you don't have to search the next box repeatedly . This is also the use of the above pruning ideas .
Just understand the key pruning points above , Then this kind of problem can be solved at will .
As for the recording path of this question, it is the test of programming skills , Needless to say, what ideas . No, just say that the coding ability is not good .
Maybe some people who don't understand analysis also hit the code right , Maybe he's lucky . Maybe he is really a genius !
Anyway, the probability is very low , The greatest chance is that his code is copied .
#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;
/*
Key understanding : Only when the next grid updates the minimum value does it need to be extended to this grid . Otherwise, there is no need to expand to this lattice . This is also equivalent to the pruning point of guangsearch . I can't understand this . There is no thorough understanding of this problem .*/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]; // Pay attention to the calculation error :p->sec = Maze[N-1][M-1] or = getSec(N-1, M-1) p->sec = getSec(N-1, M-1)-1;// The end may also be an enemy , The starting point stipulates invincible 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); } /* Key understanding : Only when the next grid updates the minimum value does it need to be extended to this grid . Otherwise, there is no need to expand to this lattice . This is also equivalent to the pruning point of guangsearch . I can't understand this , There is no thorough understanding of this problem .*//* All kinds of mistakes and lessons ! qu.push(tmp); tmp.vis = true; // Multiple errors else. Logic error else tmp->vis = true //Maze[tx][ty] = 'X'; tmp.sec = p.sec+sec; tmp.p = &mazeRec[p.x][p.y]; // error :tmp->p = p; // error :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';// Fewer mistakes -'0' for (int i = 0; i < fig; i++) { printf("%ds:FIGHT AT (%d,%d)\n", s++, x, y); } } } puts("FINISH"); } return 0;}
Copyright notice : The author Jing Xin . Landscape space address :http://blog.csdn.net/kenden23/. Reprinted only with the consent of the author .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117152.html Link to the original text :https://javaforall.cn
边栏推荐
- [translation] supply chain security project in toto moved to CNCF incubator
- map的使用(列表的数据赋值到表单,json逗号隔开显示赋值)
- How to do smoke test
- Test Li hi
- 【翻译】数字内幕。KubeCon + CloudNativeCon在2022年欧洲的选择过程
- Using clip path to draw irregular graphics
- 潇洒郎: AttributeError: partially initialized module ‘cv2‘ has no attribute ‘gapi_wip_gst_GStreamerPipe
- 1805. Number of different integers in the string
- IC设计流程中需要使用到的文件
- 理解 YOLOV1 第二篇 预测阶段 非极大值抑制(NMS)
猜你喜欢
零基础入门PolarDB-X:搭建高可用系统并联动数据大屏
Documents to be used in IC design process
深度剖析原理,看完这一篇就够了
Blue Bridge Cup microbial proliferation C language
Li Kou 101: symmetric binary tree
深入分析,Android面试真题解析火爆全网
Mysql Information Schema 学习(二)--Innodb表
反射及在运用过程中出现的IllegalAccessException异常
【基础架构】Flink/Flink-CDC的部署和配置(MySQL / ES)
面试突击63:MySQL 中如何去重?
随机推荐
mod_wsgi + pymssql通路SQL Server座
[pytorch] yolov5 train your own data set
利用 clip-path 绘制不规则的图形
10 schemes to ensure interface data security
[translation] linkerd's adoption rate in Europe and North America exceeded istio, with an increase of 118% in 2021.
深入分析,Android面试真题解析火爆全网
VMware virtual machine cannot open the kernel device "\.\global\vmx86"
From spark csc. csr_ Matrix generate adjacency matrix
Social recruitment interview experience, 2022 latest Android high-frequency selected interview questions sharing
MySql必知必会学习
LeetCode_ Double pointer_ Medium_ 61. rotating linked list
终于可以一行代码也不用改了!ShardingSphere 原生驱动问世
关于图像的读取及处理等
【计算情与思】扫地僧、打字员、信息恐慌与奥本海默
In simple terms, interview surprise Edition
Teach you to learn JS prototype and prototype chain hand in hand, a tutorial that monkeys can understand
部门树递归实现
蓝桥杯 微生物增殖 C语言
LeetCode_格雷编码_中等_89.格雷编码
面试突击63:MySQL 中如何去重?