挺不错的一道搜索题，由于数据范围大，所以用stl中的set来标记是否可走以及是否走过。
其他的就是利用bfs的性质找最短路了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 #include <set> 6 using namespace std; 7 8 typedef pair<int, int> pii; 9 set<pii> s; 10 queue< pair<pii, int> > q; 11 int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 }; 12 int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 }; 13 14 int main () 15 { 16 int x0, y0, x1, y1; 17 while ( scanf("%d%d%d%d", &x0, &y0, &x1, &y1) != EOF ) 18 { 19 s.clear(); 20 while ( !q.empty() ) q.pop(); 21 int t; 22 scanf("%d", &t); 23 while ( t-- ) 24 { 25 int r, a, b; 26 scanf("%d%d%d", &r, &a, &b); 27 for ( int k = a; k <= b; k++ ) 28 { 29 s.insert( make_pair( r, k ) ); 30 } 31 } 32 q.push( make_pair( make_pair( x0, y0 ), 0 ) ); 33 int ans = -1; 34 while ( !q.empty() ) 35 { 36 int x = q.front().first.first; 37 int y = q.front().first.second; 38 int step = q.front().second; 39 q.pop(); 40 if ( x == x1 && y == y1 ) 41 { 42 ans = step; 43 break; 44 } 45 for ( int i = 0; i < 8; i++ ) 46 { 47 pii tmp( x + dx[i], y + dy[i] ); 48 if ( s.find( tmp ) == s.end() ) continue; 49 s.erase(tmp); 50 q.push( make_pair( tmp, step + 1 ) ); 51 } 52 } 53 printf("%d ", ans); 54 } 55 return 0; 56 }