首页 > 代码库 > BFS（广度优先搜索）
BFS（广度优先搜索）
Catch That Cow
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Output
Sample Input
5 17
Sample Output
4
Hint
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> using namespace std; struct node { int x,step; }pos,q; int vis[100006]; queue<node>ans; void Push(int x,int step)//避免代码冗长 { q.x=x; vis[x]=1; q.step=step+1; ans.push(q); } int bfs(int a,int b) { int x; pos.x=a;pos.step=0; vis[a]=1; ans.push(pos); while(!ans.empty()) { pos=ans.front(); ans.pop(); if(pos.x==b) return pos.step; x=pos.x-1; if(x>=0 && x<100005 && vis[x]==0) { Push(x,pos.step); } x=pos.x+1; if(x>=0 && x<100005 && vis[x]==0) { Push(x,pos.step); } x=pos.x+pos.x; if(x>=0 && x<100005 && vis[x]==0) { Push(x,pos.step); } } return -1; } int main() { int a,b; cin>>a>>b; cout<<bfs(a,b)<<endl;; return 0; }
Knight Moves
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output For each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input
e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; char a[5],b[5]; int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; struct node { int x,y,step; }pos,ans; void bfs(int x1,int y1,int x2,int y2) { queue<node>q; int vis[11][11]; int xx,yy; pos.x=x1;pos.y=y1;pos.step=0; memset(vis,0,sizeof(vis)); vis[pos.x][pos.y]=1; q.push(pos); while(!q.empty()) { pos=q.front(); q.pop(); if(pos.x==x2 && pos.y==y2) { printf("To get from %s to %s takes %d knight moves.\n",a,b,pos.step); return ; } for(int i=0;i<8;i++) { xx=pos.x+dir[i][0]; yy=pos.y+dir[i][1]; if((xx>0 && xx<9) && (yy>0 && yy<9) && vis[xx][yy]==0) { ans.x=xx; ans.y=yy; ans.step=pos.step+1; q.push(ans); } } } } int main() { while(scanf("%s%s",a,b)!=EOF) { int x1,y1,x2,y2; x1=a[0]-‘a‘+1;y1=a[1]-‘0‘; x2=b[0]-‘a‘+1;y2=b[1]-‘0‘; bfs(x1,y1,x2,y2); } return 0; }
Ice Cave
You play a computer game. Your character stands on some level of a multilevel ice cave. In order to move on forward, you need to descend one level lower and the only way to do this is to fall through the ice.
The level of the cave where you are is a rectangular square grid of n rows and m columns. Each cell consists either from intact or from cracked ice. From each cell you can move to cells that are side-adjacent with yours (due to some limitations of the game engine you cannot make jumps on the same place, i.e. jump from a cell to itself). If you move to the cell with cracked ice, then your character falls down through it and if you move to the cell with intact ice, then the ice on this cell becomes cracked.
Let‘s number the rows with integers from 1 to n from top to bottom and the columns with integers from 1 to m from left to right. Let‘s denote a cell on the intersection of the r-th row and the c-th column as (r,?c).
You are staying in the cell (r1,?c1) and this cell is cracked because you‘ve just fallen here from a higher level. You need to fall down through the cell (r2,?c2) since the exit to the next level is there. Can you do this?
Input
The first line contains two integers, n and m (1?≤?n,?m?≤?500) — the number of rows and columns in the cave description.
Each of the next n lines describes the initial state of the level of the cave, each line consists of m characters "." (that is, intact ice) and "X" (cracked ice).
The next line contains two integers, r1 and c1 (1?≤?r1?≤?n,?1?≤?c1?≤?m) — your initial coordinates. It is guaranteed that the description of the cave contains character ‘X‘ in cell (r1,?c1), that is, the ice on the starting cell is initially cracked.
The next line contains two integers r2 and c2 (1?≤?r2?≤?n,?1?≤?c2?≤?m) — the coordinates of the cell through which you need to fall. The final cell may coincide with the starting one.
Output
If you can reach the destination, print ‘YES‘, otherwise print ‘NO‘.
Example
4 6
X...XX
...XX.
.X..X.
......
1 6
2 2
YES
5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1
NO
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
YES
题目大意，从X（缝隙中出来，最后必须回到裂缝中）但中途不能掉入裂缝中，所以只能走点上，且每个点走一次过后会开裂，因此不能走第二次，第二次一旦走上就会掉下去。
#include <iostream> #include <cstring> #include <cmath> #include <queue> using namespace std; char a[502][502]; int vis[502][502]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; struct node { int x,y; }pos,q; queue<node>ans; int bfs(int x1,int y1,int x2,int y2,int n,int m) { int xx,yy; memset(vis,0,sizeof(vis)); pos.x=x1;pos.y=y1; vis[x1][y1]=1; ans.push(pos); while(!ans.empty()) { pos=ans.front(); ans.pop(); for(int i=0;i<4;i++) { xx=dir[i][0]+pos.x; yy=dir[i][1]+pos.y; if((xx>=1 && xx<=n) && (yy>=1 && yy<=m)) { if(xx==x2 && yy==y2 && a[xx][yy]==‘X‘)return 1; if(a[xx][yy]==‘.‘ && vis[xx][yy]==0) { q.x=xx; q.y=yy; vis[xx][yy]=1; ans.push(q); a[xx][yy]=‘X‘; } } } } return 0; } int main() { int n,m,x1,y1,x2,y2; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } cin>>x1>>y1>>x2>>y2; int c=bfs(x1,y1,x2,y2,n,m); if(c==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }
Oil Deposits
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*‘, representing the absence of oil, or `@‘, representing an oil pocket.
Output For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
Sample Output
0 1 2 2
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> using namespace std; int dir[8][2]={{0,1},{0,-1},{1,-1},{1,1},{1,0},{-1,0},{-1,-1},{-1,1}}; struct node{ int x,y; }pos,q; queue<node>ans; int vis[110][110]; char a[110][110]; void bfs(int i,int j,int n,int m) { int xx,yy; pos.x=i;pos.y=j; memset(vis,0,sizeof(vis)); vis[i][j]=1; ans.push(pos); while(!ans.empty()) { pos=ans.front(); ans.pop(); a[pos.x][pos.y]=‘*‘; for(int k=0;k<8;k++) { xx=pos.x+dir[k][0]; yy=pos.y+dir[k][1]; if((xx>=0 && xx<n) && (yy>=0 && yy<m) && a[xx][yy]==‘@‘ && vis[xx][yy]==0) { q.x=xx; q.y=yy; vis[xx][yy]=1; ans.push(q); } } } while(!ans.empty()) { ans.pop(); } } int main() { int n,m; while(cin>>n>>m && (n && m)) { int sum=0; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]==‘@‘) { sum++; bfs(i,j,n,m); } } } cout<<sum<<endl; } return 0; }
BFS（广度优先搜索）