hdu 1175(广搜)

时间:2021-09-27 17:12:06

题意:容易理解...

思路:我开始的思路不好实现,而且有漏洞,时间复杂度也高,后来在网上学了下别人的方法,真心感觉很牛B,不仅代码好实现,而且时间复杂度比较低,具体看代码实现吧!!

代码实现:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;
struct node{
int x;
int y;
int count;
};
int visited[][];
int b[][]={{-,},{,},{,-},{,}};
int map[][];
int n,m;
int sx,sy,ex,ey;
int ca(int x,int y)
{
if(x>=&&x<=n&&y>=&&y<=m)
return ;
else
return ;
}
int bfs()
{
int i;
queue<node>Q;
struct node p,temp;
p.x=sx;
p.y=sy;
p.count=;
visited[sx][sy]=-;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(p.count>=)
return ;
if(p.x==ex&&p.y==ey)
return ;
for(i=;i<;i++)
{
temp.x=p.x+b[i][];
temp.y=p.y+b[i][];
while(ca(temp.x,temp.y)&&map[temp.x][temp.y]==)//把某个方向上的点全部搜完
{
if(visited[temp.x][temp.y]==)//还没访问过的点进入队列
{
visited[temp.x][temp.y]=-;
temp.count=p.count+;
if(temp.x==ex&&temp.y==ey)
{
if(temp.count<=)
return ;
else
return ;
}
Q.push(temp);
}
temp.x=temp.x+b[i][];
temp.y=temp.y+b[i][];
}
}
}
return ;
}
int main()
{
int i,j,q,temp;
while(scanf("%d%d",&n,&m)!=EOF&&(n+m)!=)
{
for(i=;i<=n;i++)
for(j=;j<=m;j++)
scanf("%d",&map[i][j]);
scanf("%d",&q);
while(q--)
{
for(i=;i<=n;i++)
for(j=;j<=m;j++)
visited[i][j]=;
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
if(map[sx][sy]==map[ex][ey]&&map[sx][sy]!=)
{
temp=map[ex][ey];
map[ex][ey]=;
if(bfs())
printf("YES\n");
else
printf("NO\n");
map[ex][ey]=temp;
}
else
printf("NO\n");
}
}
return ;
}