HDU 1175 廣度優先搜索(BFS)

題意：能不能將兩個位置的棋子(非0)消去，並不能超過兩次改變方向．

題型：廣度優先搜索(BFS)

思路：將其中的一個點作為起點，向外搜索，看能否在限制條件之內找到另一個點

個人總結：我做的時候沒考慮完全，所以沒有用數組(代碼中的num)保存到達該點時轉向最少次數，所以一直ＷＡ了！

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
#include<cctype>  
#include<iomanip>  
#include<queue>  
 
using namespace std; 
const int inf=10000000; 
 
struct node{ 
    int x,y; 
    int d; 
    int k; 
}st,rt,ne; 
 
int n,m; 
int map[1005][1005]; 
int num[1005][1005]; 
int dx[4]={0,0,1,-1}; 
int dy[4]={1,-1,0,0}; 
 
bool BFS(int x1,int y1,int x2,int y2){ 
    if(map[x1][y1]!=map[x2][y2]||!map[x1][y1])return false; 
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=m;++j) 
            num[i][j]=1000; 
    queue<node>M; 
    st.x=x1, st.y=y1, st.k=0, st.d=-1; 
    num[x1][y1]=0; 
    M.push(st); 
    while(!M.empty()){ 
        rt=M.front(); M.pop(); 
        for(int i=0;i<4;++i){ 
            ne=rt; 
            ne.x+=dx[i]; 
            ne.y+=dy[i]; 
            if(ne.x<=0||ne.y<=0||ne.x>n||ne.y>m)continue; 
            if(ne.d!=i)ne.k++; 
            ne.d=i; ///轉向一次  
            if(ne.k>3)continue;       ///超地兩次轉向  
            if(ne.x==x2&&ne.y==y2)return true;///能找到目標點  
            if(map[ne.x][ne.y])continue;//cout<<ne.x<<' '<<ne.y<<' '<<ne.k<<endl;  
            if(ne.k<num[ne.x][ne.y]){ 
                num[ne.x][ne.y]=ne.k; 
                M.push(ne); 
            } 
        } 
    } 
    return false; 
} 
 
int main(){ 
    while(~scanf("%d%d",&n,&m)&&(n||m)){ 
        for(int i=1;i<=n;++i) 
            for(int j=1;j<=m;++j) 
                scanf("%d",&map[i][j]); 
        int q; scanf("%d",&q); 
        while(q--){ 
            int x1,y1,x2,y2; 
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 
            if(BFS(x1,y1,x2,y2))puts("YES"); 
            else puts("NO"); 
        } 
    } 
    return 0; 
}