1175.cpp

杭州电子科技大学ACM-OJ系统的部分代码

#include <iostream>   //老师写的
#include <list>
using namespace std;
struct node
{
    int x;
    int y;
    int flag;
    int c;
};
list<node> current;  //广度搜索队列
node end;    //结束点
int map[1000][1000];
bool is_end(node x)//判断是否结束
{
    if((x.x==end.x)&&x.y==end.y)
        return true;
    else
        return false;
}
bool bfs(int maxx,int maxy)
{
    node t,addx,addy,subx,suby;    
    bool flag=false;
    while(current.size()!=0)   //可选点为不为O的时候进行搜索
    {
        t=current.front();   //队列头
        current.pop_front();       //出列
        subx=suby=addy=addx=t;   //4个方向是搜索
        addx.x++;
        addy.y++;
        subx.x--;
        suby.y--;
        if((addx.x<=maxx)&&(t.flag!=-1))   //没超过范围，并且不是由左方向移动得到的状态点，则向右搜索
        {
            if(is_end(addx))     //是否达到目标
            {
                flag=true;
                break;
            }
            if(map[addx.x][addx.y]==0)    //是否为空位
            {
                if((t.flag!=1)&&(t.flag!=0))            //如果前一状态不是右得到的
                    addx.c=t.c+1;       //那么出现转角
                if(addx.c<=2)           //转角大于2的话不加入新状态
                {
                    addx.flag=1;       //记录添加状态点的移动方向，1为右
                    current.push_back(addx);   //加入搜索集
                }
                
            }
        }
        if((addy.y<=maxy)&&(t.flag!=-2)) //没超过范围，并且不是由上方向移动得到的状态点，则向下搜索
        {
            if(is_end(addy))
            {
                flag=true;
                break;
            }
            if(map[addy.x][addy.y]==0)
            {
                if((t.flag!=2)&&(t.flag!=0))
                    addy.c=t.c+1;
                if(addy.c<=2)
                {
                    addy.flag=2;
                    current.push_back(addy);
                }
            }
        }
        
        if((subx.x>=0)&&(t.flag!=1))
        {
            if(is_end(subx))
            {
                flag=true;
                break;
            }
            if(map[subx.x][subx.y]==0)
            {
                if((t.flag!=-1)&&(t.flag!=0))
                    subx.c=t.c+1;
                if(subx.c<=2)
                {
                    subx.flag=-1;
                    current.push_back(subx);
                }
            }
        }
        
        if((suby.y>=0)&&(t.flag!=2))
        {
            if(is_end(suby))
            {
                flag=true;
                break;
            }
            if(map[suby.x][suby.y]==0)
            {
                if((t.flag!=-2)&&(t.flag!=0))
                    suby.c=t.c+1;
                if(suby.c<=2)
                {
                    suby.flag=-2;
                    current.push_back(suby);
                }
            }
        }
    }
    return flag;
}



bool judge(int x1,int y1)
{
    if((map[x1][y1]!=map[end.x][end.y])||(map[x1][y1]==0))
        return false;
    int maxx=x1>end.x?x1:end.x;
    int maxy=y1>end.y?y1:end.y;
    node t;
    t.x=x1;
    t.y=y1;
    t.flag=0;
    t.c=0;
    current.push_back(t);    
    if(bfs(maxx,maxy))
        return true;
    else 
        return false;
}

int main()
{
    int n,m;    
    while(cin>>n>>m,n+m)
    {
        int x1,x2,y1,y2;
        int quest;
        int i,j;
        int len;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                cin>>map[i][j];
            }
        }
        cin>>quest;
        while(quest)
        {
            cin>>x1>>y1>>x2>>y2;
            end.x=x2-1;
            end.y=y2-1;
            end.flag=0;
            end.c=2;
            if(judge(x1-1,y1-1))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
            quest--;
        }
        len=current.size();
        for(i=0;i<len;i++)
        {    
            current.pop_back();
        }

    }
    return 0;
}