首页 > 代码库 > bfs

bfs

题目链接http://qscoj.cn/problem/37/

标准的bfs模型,就直接贴代码了。

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn = 1e3+10;
 6 int n, m, x1, x2, y1, y2;
 7 typedef pair<int, int> P;
 8 string s[maxn];
 9 int d[maxn][maxn];
10 int dx[] = {1, 0, -1, 0};
11 int dy[] = {0, 1, 0, -1};
12 
13 void solve(){
14     x1--;x2--;y1--;y2--;
15     for(int i = 0; i < n; i ++) cin >> s[i];
16     memset(d, -1, sizeof(d));
17     queue<P> que;
18     que.push(P(x1,y1));
19     d[x1][y1] = 0;
20     while(que.size()){
21         P p = que.front();que.pop();
22         if(p.first == x2 && p.second == y2)break;
23         for(int i = 0; i < 4; i++){
24             int nx = p.first + dx[i], ny = p.second + dy[i];
25             if(0 <= nx && nx < n && 0 <= ny && ny < m && s[nx][ny] != 0 && d[nx][ny] == -1){
26                 que.push(P(nx, ny));
27                 d[nx][ny] = d[p.first][p.second] + 1;
28             }
29         }
30     }
31     printf("%d\n",d[x2][y2]);
32     return;
33 }
34 
35 int main(){
36     while(cin>>n>>m>>x1>>y1>>x2>>y2)
37         solve();
38     return 0;
39 }

 

bfs