HOJ.rar_HOJ_hoj2055_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; }