题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=1175
广搜有重复，所以用到一个技巧，将visit初始化大一些，当前拐弯次数小于visit时，才将当前拐弯次数赋值给visit，然后push。
不做点约束，就会超时。 详细见如下代码：
#include <iostream> #include <queue> using namespace std; int visit[1000][1000]; int t[4][2]={-1,0,1,0,0,-1,0,1}; //(x,y)四个方向向量 int maps[1001][1001]; int n,m; //n行，m列 typedef struct Point { int x; int y; }; Point point0,point1; typedef struct Status { int step; //记录拐弯数 Point point; //记录当前点位置 int direction; //记录前面的方向，用于判断拐弯 }; Status w,ww; bool legal_poistion(int x ,int y) //判断搜索的位置是否合法 { if(x>=1 && x<=n && y>=1 && y <=m) return true; else return false; } void bfs() { int i ; queue<Status>m_queue; m_queue.push(w); while(!m_queue.empty()) { ww = m_queue.front(); m_queue.pop(); if(ww.step >2) continue; for(i =0;i<4;i++) { w = ww; w.point.x +=t[i][0]; w.point.y +=t[i][1]; w.direction = i;//四个方向 if(legal_poistion(w.point.x ,w.point.y)&&(maps[w.point.x][w.point.y]==0 || (w.point.x == point1.x && w.point.y ==point1.y))) { if(ww.direction!=300 && w.direction !=ww.direction)//第一个原地位置方向设置为ww300 w.step++; if(w.step>2) continue; if(visit[w.point.x][w.point.y] >= w.step) //将可以小step数到达的存入队列中 { //加快搜索,否则会超时 visit[w.point.x][w.point.y] = w.step; m_queue.push(w); } if(w.point.x == point1.x && w.point.y == point1.y)//可以到达目的地，则输出YES { printf("YES\n"); return ; } } } } printf("NO\n"); return ; } int main() { int i; int j; int case_number; while(scanf("%d%d",&n,&m)!=EOF && (n+m)!=0) { for(i=1 ;i<=n;i++) for (j =1;j<=m;j++) scanf("%d",&maps[i][j]); scanf("%d",&case_number); for(;case_number >=1;case_number--) { scanf("%d %d %d %d",&point0.x ,&point0.y,&point1.x,&point1.y); if(maps[point0.x][point0.y]==0|| maps[point0.x][point0.y]!=maps[point1.x][point1.y]) {//如果两者对应块类型不一致或者有一个为空，则返回No printf("NO\n"); continue; } memset(visit,1,sizeof(visit)); w.point.x = point0.x; w.point.y = point0.y; w.direction = 300; //这里注意开始起点的，假设方向是任意的 w.step =0; visit[point0.x][point0.y] = 0; bfs(); } } return 0; }