前面的篇幅占了太多,再次新开一章,讲述BFS求最短路的问题
注意此时DFS就没有BFS好用了,因为DFS更适合求全部解,而BFS适合求最优解
这边再次提醒拓扑变换的思想在图形辨认中的重要作用,需要找寻不同图形在进行拓扑变换时候的不变性
假设有一个网格迷宫,由n行m列的单元格组成,每个单元格要么是空地,要么是障碍物,如何找到从起点到终点的最短路径?
回想二叉树的BFS,节点的访问顺序恰好是他们到根节点距离从小到大的顺序,类似的可以用BFS来按照到起点的距离顺序遍历迷宫图(因为BFS保证了后面遍历到的点离起点的距离是不严格单调递增的)
易知道如果将前一步指向后一步这一种关系当作树的祖孙层次关系,那么就可以创建出来一棵树,很明显这棵树的一大特点在于如果路权相等的情况下,局部最优会达到全局最优,即贪心的利用,使得除根节点之外,其他节点一定有且只有一个父亲节点,这棵树被称为最短路树,或者BFS树
Abbott's_Revenge题解
点击查看代码
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxl = 11;
const int maxword = 20+5;
int toward[4][2] = {-1,0,0,1,1,0,0,-1}, dic[maxl][maxl][4][3];
struct Point{
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
};
struct Node{
int x, y, from;//0 1 2 3 nesw 012 go l f r
vector<Point> v[4];
}node[maxl][maxl];
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
char name[maxword];
while(scanf("%s", name) == 1 && strcmp(name, "END")) {
int sx, sy, ex, ey;
char sdic;
cin >> sx >> sy >> sdic >> ex >> ey;
memset(node, 0, sizeof(node));
memset(dic, 0, sizeof(dic));
int tx, ty;
while(scanf("%d", &tx) == 1 && tx) {
scanf("%d", &ty);
node[tx][ty].x = tx;
node[tx][ty].y = ty;
char buf[10];
while(scanf("%s", buf)==1 && strcmp(buf, "*")) {
int d;
switch(buf[0]) {
case 'N': d=0; break;
case 'E': d=1; break;
case 'S': d=2; break;
case 'W': d=3; break;
default: break;
}
for(int i = 1; i < strlen(buf); i++) {
switch(buf[i]) {
case 'L': dic[tx][ty][d][0] = 1; break;
case 'F': dic[tx][ty][d][1] = 1; break;
case 'R': dic[tx][ty][d][2] = 1; break;
default : break;
}
}
}
}
int d;
switch(sdic) {
case 'N': d=0; break;
case 'E': d=1; break;
case 'S': d=2; break;
case 'W': d=3; break;
default: break;
}
dic[sx][sy][d][1] = 0;
int sx1 = sx+toward[d][0], sy1 = sy+toward[d][1];
node[sx1][sy1].x = sx1;
node[sx1][sy1].y = sy1;
node[sx1][sy1].v[d].push_back(Point(sx, sy));
node[sx1][sy1].v[d].push_back(Point(sx1, sy1));
node[sx1][sy1].from = d;
queue<Node> q;
q.push(node[sx1][sy1]);
vector<Point> ans;
while(!q.empty()) {
Node n = q.front();
q.pop();
if(n.x == ex && n.y == ey) {
ans = n.v[n.from];
break;
}
int temp = n.from;
for(int i = 0; i < 3; i++) {
if(dic[n.x][n.y][temp][i]) {
int ndis = (temp+4+i-1)%4, sum = 10;
int px = n.x+toward[ndis][0], py = n.y+toward[ndis][1];
// for(int j = 0; j < 3; j++) {
// sum += dic[px][py][ndis][j];
// }
if(sum) {
Node insert;
insert.x = px;
insert.y = py;
insert.from = ndis;
insert.v[ndis] = n.v[n.from];
insert.v[ndis].push_back(Point(px, py));
q.push(insert);
}
dic[n.x][n.y][temp][i] = 0;
}
}
}
cout << name << endl;
if(ans.empty()) cout << " No Solution Possible" << endl;
else{
for(int i = 0; i < ans.size(); i++) {
if(i%10 == 0) cout << " ";
cout << "(" << ans[i].x << "," << ans[i].y << ")";
if(i%10 == 9) cout << endl;
else if(i != ans.size()-1) cout << " ";
}
if(ans.size()%10) cout << endl;
}
}
return 0;
}
笔者终于自行编出这段代码了,不过还是借用了udebug的调试,自己的思想还是不够严谨,不过笔者并没有看过他人代码参考,这题除了模拟比较高人心态之外,其思想是比较简单的,即不重不漏走完全图,有bfs路的出现就有答案,否则没有答案,需要注意的是对于各个结点的存储方式以及如何判断朝向,这两大问题解决了,本题就会较为简单了,本题的难点是对多数据的存储以及处理
需要注意的是在这题貌似PE的显示是WA,笔者只是修改了输出格式就AC了,只能说UVAOJyyds,这边读者有兴趣的话一定要注意这个坑
这道题是作者强烈要求搞懂细节,并且能够独立编写程序的题目,因此笔者会尽量将作者原先的代码写满注释,方便后来的读者能够更加方便的理解本道题目
这边小插入一下关于unique的使用,注意一定要先排序再使用,否则会出现很多意想不到的错误,同时这部分的内容感觉和迭代器有很大的关系,什么时候作者补充了这方面的知识,再在后面填坑吧
点击查看代码
/*
本题和普通的迷宫在本质上是一样的,但是由于“朝向”也起到了关键作用,所以需要用一个三元组(注意这边的三元组的利用,这是对于线性代数
的一个高级理解,直接跳过结构体,直接用简单的数组来模拟,不过本题确实可以直接通过数组来模拟,使用结构体,只是为了形式上的统一罢了)
(r,c,dir)表示位于(r,c)面朝dir这个状态,这边是笔者认为最妙的地方,这种存储方阵数据的思想值得学习。假设入口位置为(r0,c0),朝向为dir
则初始状态并不是(r0,c0,dir),而是(r1,c1,dir),其实这边的dir表示的是上一步是从那个方向来的(描述不够严谨),所以从起点开始,会使得
这边的递归思想不够完备,递归思想的一大要求就是需要里面的对象在一定程度上是等价的,也就是各方面的状态属性应该是近似一致的
此处用d[r][c][dir]表示初始状态到(r,c,dir)的最短路长度,并且用p[r][c][dir]保存了状态(r,c,dir)的BFS树中的父节点,这样就可以不用特定
建立一个vector数组来实现该功能了,这边的结构成立的条件之一就是r,c,dir的父节点最多只有一个
*/
const char* dirs = "NESW"; //顺时针旋转 //注意这边的深意,一般来讲确定一个顺序顺时针逆时针可以根据个人喜好,因为这样子才能通过一种类似圆排列的方式来进行抽象的统一
const char* turns = "FLR"; //一样的目的,笔者这边就不再赘述了
int dir_id(char c) { return strchr(dirs, c) - dirs; } //这个函数的作用是返回c所在的第几个位置,范围是[0, strlen(dirs))
int turn_id(char c) { return strchr(turns, c) - turns; }//与上面的函数作用是一样的
//接下来是行走函数,根据当前状态和转弯方式,计算出后续状态
const int dr[] = {-1, 0, 1, 0};//这边作者用两个一维数组实现笔者二维数组的效果,分别是NESW
const int dc[] = {0, 1, 0, -1};
Node walk(const Node& u, int turn) {//这边就是通过012控制,0不改变方向,1l本质上就是逆时针-1,2r本质上就是顺时针+1
int dir = u.dir;
if(turn == 1) dir = (dir + 3) % 4; //逆时针
if(turn == 2) dir = (dir + 1) % 4; //顺时针
return Node(u.r + dr[dir], u.c + dc[dir], dir); //返回刷新过的新节点(nr,nc,ndir)
}
//输入函数比较简单,作用就是读取r0,c0,dir,并且计算出r1,c1,然后读入has_edge数组,其中has_edge[r][c][dir][turn]表示当前状态是(r,c,dir),是否可以沿着转弯方向turn行走,接下来就是最常见的BFS的主过程了
void solve() {
queue<Node> q;
memset(d, -1, sizeof(q));
Node u(r1, c1, dir);//注意是r1不是r0
d[u.r][u.c][u.dir] = 0;//这边开始计数
//笔者认为这边有一个bug,这边忘了记录r1,c1的父节点了,不知道是不是作者打漏了
q.push(u);
while(!q.empty()) {//BFS开始
Node u = q.front(); q.pop();//q.pop()不要忘掉,不然就会成为一个死循环,或者爆栈了
if(u.r == r2 && u.c == c2) { print_ans(u); return; }//如果到了最终的结点进行输出
for(int i = 0; i < 3; i++) {
Node v = walk(u, i);//这边会先进行行走,笔者认为这边先判断能否走可能效率更高?
if(has_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0) {//第一个条件是是否可以往这边走,第二个条件是判断是否有这个点?作者没有给出任何信息,qaq,第三个条件判断的是该方向并没有来过,也就是变相的保证了每个结点最多有一个父节点
d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;//如果前面的条件都符合,那么开始建立新节点,同时计数
p[v.r][v.c][v.dir] = u;//记录父节点,BFS树
q.push(v);//老BFS了
}
}
}
printf("No Solution Possible\n");//如果没有找到才会执行该段代码
}
//最后是解的打印过程,它也可以写成递归函数,不过用vector保存节点可以避免递归时出现栈溢出,并且更加灵活,注意如果递归的话,注意先序遍历的写法,应该是先递归后输出
//使用BFS求出图的最短路之后,可以用递归方式打印最短路的具体路径。如果最短路非常长,递归可能会引起栈溢出,此时可以改用循环,用vector保存路径
void print_ans(Node u) {
//从目标结点逆序追朔到初始节点
vector<Node> nodes;
for(;;) {
nodes.push_back(u);
if(d[u.r][u.c][u.dir] == 0) break;//开始追溯上一个父节点的位置,最后输出的时候需要逆序输出,同时注意这边的边界条件就是0,这个在最初的设置中很容易想到
u = p[u.r][u.c][u.dir];//我愿称之为伪递归
}
nodes.push_back(Node(r0, c0, dir));//好吧,笔者前面的论断是错误的,作者还是作者,将这边最初的结点给加入进去了
//打印解,每行10个
int cnt = 0;
for(int i = nodes.size()-1; i >= 0; i--) {//最后就是经典环节打印输出环节了,如果对这个还不熟悉的读者,可以去前几张找几套simulate题练练手
if(cnt % 10 == 0) print(" ");//保证开头是" "
printf(" (%d,%d)", nodes[i].r, nodes[i].c);//记住是逆序输出,就可以了
if(++cnt % 10 == 0) printf("\n");//注意这边对于\n的输出的控制
}
if(nodes.size() % 10 != 0) printf("\n");
}
以上就是笔者对于作者代码的解读与思考,只能说作者赛高,思路非常清晰
手机扫一扫
移动阅读更方便
你可能感兴趣的文章