本文介绍了一种迷宫寻路算法，重点在于如何利用广度优先搜索（BFS）找到从一个位置到另一个位置的路径，同时考虑了行走过程中的转弯次数限制。文章通过具体的示例说明了算法实现细节，并分享了调试过程中的经验教训。
给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x 1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数，(x 1, y 1), (x 2, y 2)表示两个位置，其中x 1，x 2对应列，y 1, y 2对应行。
2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3
no yes
首先检讨一下自己：要认真读题，不要自大，不要中途放弃，不要怀疑自己。不得不说这道题让我心态奔溃，只是因为我感觉这道题很简单，然而一次次的wa让我失去了原有的信心。今天下了大雪，我早上写的这道题，感觉一发就过了，然而事与愿违，我又匆匆改了一下，想快点过了，因为室友喊我去打雪仗，然而我还没有过，我渐渐的就急了，当时思绪就乱了，一是因为室友催我，二是我不该因为这样的题而消磨时间，我感觉这就是一种耻辱，我感觉妄为中国人，连这个题就搞不定。可是此时我心态已经炸了，我又交了几发还不过，然后我就放弃了，出去打了波雪仗。玩完吃过饭，又匆匆来写这道题，最后在不断调试下才发现漏洞百出！（不要问我为什么有那么多废话，我只想说，我要让自己记忆深刻一点。以后哪怕是一道a+b的题，我也要用心对待，不能小瞧）我以后将认真面对每道题，我不会放弃，我爱学习。下次再这样，就将十万吨屎塞队友嘴里，就诅咒我今年找不到女朋友，就诅咒室友的孩子没屁眼，我将会铭记这一天，一个白色的周四。好了检讨完毕，开始博客！
第一：要搞清楚坐标系。 很多迷宫中的x，y和数学中的坐标系都是反的，但是这道题说的很清楚，这一点我注意到了，可最后还是搞混了。
第二：标记数组， 标记数组不能用来标记是否走过，而是用来标记走到某点时所用到的转弯次数，假如v[x][y] = 3，表示经过(x,y)这点最优的转弯次数是3，如果接下来又有一个要经过(x,y) 且它的转弯次数是2，那么就要更新v[x][y] = 2然后再重新压入队列。
第三： 判断条件，yes的判断标准是当到达目标点，并且转弯次数<= k ，而no的判断标准是没有yes，所以no只有在整个题图跑完之后才会出现！
具体代码：
#include <queue> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; int m, n; int k, x1, y1, x2, y2; int v[105][105]; char Map[105][105]; int dr[3][3];//表示方向 int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; struct node{ int d; //上次的方向 int numd;//转弯次数 int x, y; }pre, nex; void init() { dr[0][1] = 1;//-1 0 因为下标不能为-1,所以我将x，y同时加1 dr[2][1] = 2;// 1 0 dr[1][0] = 3;//0 -1 dr[1][2] = 4;// 0 1 memset(v, -1, sizeof(v)); } bool MAP(int x,int y) { return x>=1 && y>=1 && x<=m && y<=n; } void bfs() { queue<node> q; while(!q.empty()) q.pop(); pre.x = x1; pre.y = y1; pre.d = 0; pre.numd = 0; v[x1][y1] = 0; q.push(pre); while(!q.empty()) { nex = q.front(); q.pop(); if(nex.x == x2 && nex.y == y2 && nex.numd <= k) { //判断yes printf("yes\n"); return ; } for(int i = 0; i < 4; i++) { pre.x = nex.x + d[i][0]; pre.y = nex.y + d[i][1]; pre.d = dr[d[i][0]+1][d[i][1]+1]; //方向 pre.numd = nex.numd; //次数 if(MAP(pre.x,pre.y) && Map[pre.x][pre.y] == '.') { if(nex.d != 0 && nex.d != pre.d) //判断 pre.numd = pre.numd + 1; if(v[pre.x][pre.y] == -1 || v[pre.x][pre.y] >= pre.numd) { v[pre.x][pre.y] = pre.numd; q.push(pre); } } } } puts("no"); //如果没有yes 就输出no return ; } int main() { int N; scanf("%d",&N); while(N--) { init(); scanf("%d%d",&m, &n); for(int i = 1; i <= m; i++) scanf("%s",Map[i]+1); scanf("%d%d%d%d%d",&k, &y1, &x1, &y2, &x2); bfs(); } return 0; }
扫一扫
496
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
