来源：http://acm.hdu.edu.cn/showproblem.php?pid=1175
题意：玩过连连看就一定知道（中文的）不多说了；
思路：在bfs上加一个corner数组，表示转角数；特别注意的是corner[next.x][next.y]>=temp，不能用>。不然就WA。在这里WA了好多次。。。网上查了才发现；
AC代码：
#include<iostream>#include<queue>using namespace std;typedef struct { int x,y;//坐标 int s;//s=-1为初始，1为向下，2为向上，3为向左，4为向右}node;int di[4][2]={{1,0},{-1,0},{0,-1},{0,1}};//下，上，左，右int map[1005][1005];int corner[1005][1005];int n,m;bool bfs(int x,int y,int x1,int y1){ queue<node> q; node first,next; int i,temp; first.x=x;first.y=y;first.s=-1; corner[x][y]=0; q.push(first); while(!q.empty()) { first=q.front(); q.pop(); for(i=0;i<4;i++) { next.x=first.x+di[i][0]; next.y=first.y+di[i][1]; if(next.x<n&&next.x>=0&&next.y<m&&next.y>=0) if(map[next.x][next.y]==0||(next.x==x1&&next.y==y1)) { next.s=i; if(next.s!=first.s) temp=corner[first.x][first.y]+1; else temp=corner[first.x][first.y]; if(temp<=3&&corner[next.x][next.y]>=temp) { corner[next.x][next.y]=temp; if(corner[x1][y1]<=3) return 1; q.push(next); } } } } return 0;}int main(){ int count,i,j,k,x,y,x1,y1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&map[i][j]); scanf("%d",&count); for(k=0;k<count;k++) { for(i=0;i<n;i++) for(j=0;j<m;j++) corner[i][j]=10000000; scanf("%d%d%d%d",&x,&y,&x1,&y1); if(map[x-1][y-1]!=map[x1-1][y1-1]||map[x-1][y-1]==0||map[x1-1][y1-1]==0||!bfs(x-1,y-1,x1-1,y1-1)||(x1==x&&y1==y)) printf("NO/n"); else printf("YES/n"); } } return 0;}
总结：bfs挺经典的题目，开始做个连连看小游戏玩玩。。呵呵
