前面的篇幅占了太多,再次新开一章,讲述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,这边读者有兴趣的话一定要注意这个坑