bfs+STL cf242c

 1 #include <iostream>
 2 #include <map>
 3 #include <cstdio>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 map<int, map<int,int> >mp;
 9 queue<int> q;
10 
11 int main()
12 {
13     int x0,y0,x1,y1,n;
14     while(scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&n)!=EOF)
15     {
16         int r,a,b;
17         for(int i=0;i<n;i++)
18         {
19             scanf("%d%d%d",&r,&a,&b);
20             for(int t=a;t<=b;t++)
21             {
22                 mp[r][t]=-1;
23             }
24         }
25         q.push(x0);
26         q.push(y0);
27         q.push(0);
28         int ans=-1;
29         while(!q.empty())
30         {
31             int tx=q.front();
32             q.pop();
33             int ty=q.front();
34             q.pop();
35             int cnt=q.front();
36             q.pop();
37             if(tx==x1&&ty==y1)
38             {
39                 ans=cnt;
40                 break;
41             }
42             for(int i=-1;i<=1;i++)
43             {
44                 for(int j=-1;j<=1;j++)
45                 {
46                     if(i==0&&j==0)
47                         continue;
48                     if(mp[tx+i][ty+j]==-1)
49                     {
50                         mp[tx+i][ty+j]=1;
51                         q.push(tx+i);
52                         q.push(ty+j);
53                         q.push(cnt+1);
54                     }
55                 }
56             }
57         }
58         cout<<ans<<endl;
59     }
60     return 0;
61 }
View Code