pku 1101 bfs

向右看齐 2022-08-13 12:37 166阅读 0赞

/\* //很很很经典的bfs, 这也是我第一次正式用bfs来刷题, 感受颇深: //one.cpp是用bfs来解决从一个点到另一个点的最短路程长度的方法(写的有点冗杂) 注意的几点: 1.为什么用bfs而不是dfs来解决最短路径长度问题? dfs搜索到另一个点后将所经历的点设为visited,不能再次访问; 而bfs是宽度优先的策略,则可以涉及每一条路径. 故,求一个可行解的问题(判断是否有路径)的问题适于用dfs, 最优解,最短路径等求优化解的问题适于用bfs. 2.怎样求最短路径长度? 用一个等大的二维数组记录,记录到达所经过的每一点的路径长度,最先到达的距离最短. //two.cpp 求最短路径上的转弯的线段数 在某一个的方向上所经历的点全部入队(不超界),再让先进的先出... 就可以计算出一共拐了几次弯. (这种方法十分巧妙!) 这类似于游戏"连连看"(一次只能拐两个弯,共三条线段). \*/ //one.cpp \#include <iostream> \#include <queue> using namespace std; struct Node \{ int x,y; \}; queue<Node> q; bool map\[80\]\[80\]; int value\[80\]\[80\]; int m,n; int x1,y1,x2,y2; int bfs() \{ Node d; d.x = x1, d.y = y1; q.push(d); value\[x1\]\[y1\] = 0; while(!q.empty()) \{ Node temp = q.front(); x1 = temp.x, y1 = temp.y; if(x1 == x2 && y1 == y2) break; q.pop(); if(x1-1 >= 0 && value\[x1-1\]\[y1\]==-1 && map\[x1-1\]\[y1\]) \{ Node d1; d1.x = x1-1, d1.y = y1; q.push(d1); value\[x1-1\]\[y1\] = value\[x1\]\[y1\]+1; \} if(y1-1 >= 0 && value\[x1\]\[y1-1\]==-1 && map\[x1\]\[y1-1\]) \{ Node d2; d2.x = x1, d2.y = y1-1; q.push(d2); value\[x1\]\[y1-1\] = value\[x1\]\[y1\]+1; \} if(x1+1 <= m+1 && value\[x1+1\]\[y1\]==-1 && map\[x1+1\]\[y1\]) \{ Node d3; d3.x = x1+1, d3.y = y1; q.push(d3); value\[x1+1\]\[y1\] = value\[x1\]\[y1\]+1; \} if(y1+1 <= n+1 && value\[x1\]\[y1+1\]==-1 && map\[x1\]\[y1+1\]) \{ Node d4; d4.x = x1, d4.y = y1+1; q.push(d4); value\[x1\]\[y1+1\] = value\[x1\]\[y1\]+1; \} \} return value\[x2\]\[y2\]; \} int main() \{ int cnt1 = 0; char ch; while(cin >> n >> m && !(n==0&&m==0))//n:列 m:行 \{ getchar(); for(int j = 0; j <= n+1; ++j) map\[0\]\[j\] = true; for(int j = 0; j <= n+1; ++j) map\[m+1\]\[j\] = true; for(int i = 1; i <= m; ++i) \{ map\[i\]\[0\] = true; for(int j = 1; j <= n; ++j) \{ ch = getchar(); if(ch == ' ') map\[i\]\[j\] = true; else map\[i\]\[j\] = false; \} getchar(); map\[i\]\[n+1\] = true; \} printf("Board \#%d:/n", ++cnt1); int cnt2 = 0; while(cin >> y1 >> x1 >> y2 >> x2 && !(x1==0&&y1==0&&x2==0&&y2==0)) \{ while(!q.empty()) q.pop(); memset(value, -1, sizeof(value)); map\[x2\]\[y2\] = true; if(bfs() != -1) printf("Pair %d: %d segments./n", ++cnt2, value\[x2\]\[y2\]-1); else printf("Pair %d: impossible./n", ++cnt2); map\[x2\]\[y2\] = false; \} printf("/n"); \} return 0; \} //two.cpp \#include <iostream> \#include <queue> using namespace std; struct Node \{ int x,y; \}; int x\[4\] = \{1, -1, 0, 0\}; int y\[4\] = \{0, 0, 1, -1\}; queue<Node> q; bool map\[80\]\[80\]; int value\[80\]\[80\]; int m,n; int x1,y1,x2,y2; bool ok(int i, int j) \{ if(i < 0 || j < 0 || i > m+1 || j > n+1) return false; return true; \} int bfs() \{ Node d; d.x = x1, d.y = y1; q.push(d); value\[x1\]\[y1\] = 0; while(!q.empty() && value\[x2\]\[y2\] == -1) \{ for(int i = 0; i < 4; ++i) \{ int tempx = q.front().x + x\[i\]; int tempy = q.front().y + y\[i\]; while(ok(tempx, tempy) && map\[tempx\]\[tempy\] && value\[tempx\]\[tempy\] == -1) \{ Node d; d.x = tempx, d.y = tempy; q.push(d); value\[tempx\]\[tempy\] = value\[q.front().x\]\[q.front().y\] + 1; tempx += x\[i\]; tempy += y\[i\]; \} \} q.pop(); \} return value\[x2\]\[y2\]; \} int main() \{ int cnt1 = 0; char ch; while(cin >> n >> m && !(n==0&&m==0))//n:列 m:行 \{ getchar(); for(int j = 0; j <= n+1; ++j) map\[0\]\[j\] = true; for(int j = 0; j <= n+1; ++j) map\[m+1\]\[j\] = true; for(int i = 1; i <= m; ++i) \{ map\[i\]\[0\] = true; for(int j = 1; j <= n; ++j) \{ ch = getchar(); if(ch == ' ') map\[i\]\[j\] = true; else map\[i\]\[j\] = false; \} getchar(); map\[i\]\[n+1\] = true; \} printf("Board \#%d:/n", ++cnt1); int cnt2 = 0; while(cin >> y1 >> x1 >> y2 >> x2 && !(x1==0&&y1==0&&x2==0&&y2==0)) \{ while(!q.empty()) q.pop(); memset(value, -1, sizeof(value)); map\[x2\]\[y2\] = true; if(bfs() != -1) printf("Pair %d: %d segments./n", ++cnt2, value\[x2\]\[y2\]); else printf("Pair %d: impossible./n", ++cnt2); map\[x2\]\[y2\] = false; \} printf("/n"); \} return 0; \}