连连看 优先对列 应用2
连连看 优先对列 应用2
1944864971 发表于2年前
连连看 优先对列 应用2
  • 发表于 2年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

http://acm.hdu.edu.cn/showproblem.php?pid=1175

/*
难点是 判断当前的方向与上一次的方向是否相同

用优先队列取出每次拐弯次数的最小的 然后在进行处理

*/

include

include

include

using namespace std;
int mi[1002][1002];
int vis[1002][1002];
int m,n;
struct node
{
int x;
int y;
int fX;
int num;
friend bool operator <(node a,node b)
{
return a.num>b.num;//次数小的优先取出
}
};
int dir[4][2]={0,1,1,0,0,-1,-1,0};
bool bfs(int sx,int sy,int ex,int ey)
{
node a;
a.x=sx;
a.y=sy;
a.num=-1;//拐弯的次数 因为初始方向不同于任何方向 所以第一次向任何方向走都是一次拐弯 故置为-1;
a.fX=-1;
vis[a.x][a.y]=1;
priority_queue q;
q.push(a);
while(!q.empty())
{
a=q.top();
q.pop();
for(int i=0;i<4;i++)
{
node b;
b.x=a.x+dir[i][0];
b.y=a.y+dir[i][1];
if(a.fX!=i)
{
b.fX=i;
b.num=a.num+1;
}
else
{
b.fX=a.fX;
b.num=a.num;
}
if(b.num>2)
continue;
if(b.x<=0||b.y<=0||a.x>m||b.y>n)
continue;
if(mi[b.x][b.y]==0&&vis[b.x][b.y]==0)//只能走0位置
{
vis[b.x][b.y]=1;
q.push(b);
}
if(b.x==ex&&b.y==ey&&b.num<=2)
return true;
}
}
return false;
}

int main()
{
while(scanf("%d%d",&m,&n)&&m||n)
{
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mi[i][j]);
int t;
scanf("%d",&t);
while(t--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(mi[a][b]!=mi[c][d]||mi[a][b]==0||mi[c][d]==0)
{
printf("NO\n");
continue;
}
memset(vis,0,sizeof(vis));
if(bfs(a,b,c,d))printf("YES\n");
else printf("NO\n");
}
}

return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: