题意：给出起点和终点的棋子，不能经过别的棋子，而且转弯的次数不能超过2次，问能否消除
和逃离迷宫一样，每个节点记录下来它的当前的方向和转弯的次数，再搜
注意特判起点的棋子和终点的棋子为0或者不一样的情况，这样的话就不用搜了，直接输出NO
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=1000005; 17 18 int g[1005][1005]; 19 int turn[1005][1005]; 20 int n,m; 21 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 22 23 struct node{ 24 int x,y; 25 int turn; 26 int dir; 27 }; 28 29 node st,en; 30 31 void bfs(){ 32 queue<node> q; 33 node u; 34 u.x=st.x;u.y=st.y;u.turn=0;u.dir=-5; 35 turn[u.x][u.y]=0; 36 q.push(u); 37 38 while(!q.empty()){ 39 u=q.front();q.pop(); 40 41 node v; 42 for(int i=0;i<4;i++){ 43 v.x=u.x+dir[i][0]; 44 v.y=u.y+dir[i][1]; 45 v.turn=u.turn; 46 v.dir=u.dir; 47 48 if(u.x==en.x&&u.y==en.y&&u.turn<=2){ 49 printf("YES "); 50 return; 51 } 52 if(v.dir!=i&&v.dir!=-5) v.turn++; 53 54 if(v.x==en.x&&v.y==en.y&&v.turn<=2){ 55 printf("YES "); 56 return; 57 } 58 59 if(v.x<1||v.x>n||v.y<1||v.y>m||g[v.x][v.y]!=0) continue; 60 61 if(v.turn>2) continue; 62 63 if(v.turn<=turn[v.x][v.y]){ 64 turn[v.x][v.y]=v.turn; 65 v.dir=i; 66 q.push(v); 67 } 68 } 69 } 70 printf("NO "); 71 } 72 73 int main(){ 74 while(scanf("%d %d",&n,&m)!=EOF&&n&&m){ 75 for(int i=1;i<=n;i++){ 76 for(int j=1;j<=m;j++) cin>>g[i][j]; 77 } 78 79 int q; 80 scanf("%d",&q); 81 while(q--){ 82 for(int i=1;i<=n;i++) 83 for(int j=1;j<=m;j++) turn[i][j]=1000000; 84 scanf("%d %d %d %d",&st.x,&st.y,&en.x,&en.y); 85 86 if(g[st.x][st.y]!=g[en.x][en.y]||!g[st.x][st.y]||!g[en.x][en.y]) printf("NO "); 87 else bfs(); 88 } 89 } 90 return 0; 91 }