重新开始做搜索题，发现理论和应用还是有很大的差别的。。。。
题意：给出一个有1*1的小矩形组成的大矩形，矩形的边可能是墙，也可能是门，要出（0,0）点到达给定的一个点，问最少要过几个门。
解题过程：首先，discuss里面说，给出的点不一定在给出的矩形里，如果不在直接输出0。然后就是建图了，其实这题思路很简单，但是建图麻烦，刚开始的时候，按题目中给出的方法建图，用一条线段的左下点记录，但是这样只是记录了线段的状态，并没有建图，然后参考了下面的Blog建图才AC的，但是还是ML了几次，我发现在题目中随机定义变量会很浪费内存，所以最好提前定义好所有变量，也可以重复利用变量。
http://www.cnblogs.com/longdouhzt/archive/2011/09/03/2165490.html
代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <math.h> #define N 210 using namespace std ; struct node { int x , y; int step ; //优先队列，按穿过的门数最少的路径开始扩展下去 friend bool operator<(struct node a , struct node b ) { return a.step > b.step ; } }p , tr ; priority_queue<node>q ; int map[N][N][2] , f[N][N] ;//f[][]是用矩形的左下坐标标记这个小矩形，map[i][j][d]表示左下点为i,j，方向为d的线段 int main() { int n , m , i , j , flag ; int x_min , x_max , y_min , y_max ; int tx , ty , td , t ; double si , ei ; //d[]表示从一小矩形里出去的顺序为下，左，右，上。 //dx[],dy[]表示一条线段的坐标。 //dxx[],dyy[]表示要进入的小矩阵的左下坐标。 int d[4] = {0,1,1,0} , dx[4] = {0,0,1,0} , dy[4] = {0,0,0,1}; int dxx[4] = {0,-1,1,0} , dyy[4] = {-1,0,0,1}; while ( scanf ( "%d%d" , &n , &m ) != EOF ) { if ( n == -1 && m == -1 ) break; memset( map , 0 , sizeof ( map )); memset( f , 0 , sizeof( f )); x_min = y_min = N ; x_max = y_max = -1 ; for ( i = 1 ; i <= n ; i++ ) { scanf ( "%d%d%d%d" , &tx , &ty , &td , &t ); for ( j = 0 ; j < t ; j++ ) map[tx+j*(1-td)][ty+j*td][td] = -1 ;//线段是墙 if ( tx < x_min ) x_min = tx ; if ( tx > x_max ) x_max = tx ; if ( ty < y_min ) y_min = ty ; if ( ty > y_max ) y_max = ty ; } for ( i = 1 ; i <= m ; i++ ) { scanf ( "%d%d%d" , &tx , &ty , &td ); map[tx][ty][td] = 1 ;//线段是门 if ( tx < x_min ) x_min = tx ; if ( tx > x_max ) x_max = tx ; if ( ty < y_min ) y_min = ty ; if ( ty > y_max ) y_max = ty ; } scanf ( "%lf%lf" , &si , &ei ); //优化，如果点不在矩阵里，直接输出0 if ( si < x_min || si > x_max || ei < y_min || ei > y_max ) { printf ( "0\n" ); continue ; } //取左下坐标 int xi = floor( si ); int yi = floor( ei ); while ( !q.empty()) q.pop(); p.x = xi ; p.y = yi ; p.step = 0 ; q.push( p ); f[xi][yi] = 1 ; flag = 0 ; while( !q.empty()) { tr = q.top(); q.pop(); //tx = tr.x ; ty = tr.y ; if ( tr.x < x_min || tr.x >= x_max || tr.y < y_min || tr.y >= y_max ) { flag = 1 ; break ; } for ( i = 0 ; i < 4 ; i++ ) { tx = tr.x + dx[i] ; ty = tr.y + dy[i] ; int t_x = tr.x + dxx[i] ; int t_y = tr.y + dyy[i] ; if ( map[tx][ty][d[i]] >= 0 && !f[t_x][t_y] ) { f[t_x][t_y] = 1 ; p.x = t_x ; p.y = t_y ; p.step = tr.step + map[tx][ty][d[i]] ; q.push( p ); } } } if ( flag ) printf ( "%d\n" , tr.step ); else printf ( "-1\n" ); } return 0 ; }