HDOJ1728(限制转弯的迷宫问题)
2024-09-03 05:08:24
用bfs进行深搜,求出每个可达点的最小转弯数
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_N=;
char g[MAX_N][MAX_N];
int vis[MAX_N][MAX_N];
int n,m;
int k,sx,sy,ex,ey;
struct node{
int x,y,turns;
node(){}
node(int cy,int cx,int cturns):x(cx),y(cy),turns(cturns){}
};
int dx[]={,,-,};
int dy[]={,,,-};
bool judge(int r,int c)
{
if(<=r&&r<=m&&<=c&&c<=n&&g[r][c]=='.')
{
return true;
}
return false;
}
void bfs()
{
if(sy==ey&&sx==ex)
{
printf("yes\n");
return;
}
queue<node> que;
que.push(node(sy,sx,-));
vis[sy][sx]=;
while(!que.empty())
{
node now=que.front();que.pop();
for(int i=;i<;i++)
{
int ny=now.y+dy[i];
int nx=now.x+dx[i];
while(judge(ny,nx))//按一条路深搜
{
if(!vis[ny][nx])
{
// printf("%c (%d,%d) %d\n",g[ny][nx],ny,nx,now.turns+1);
que.push(node(ny,nx,now.turns+));
vis[ny][nx]=;
if(ny==ey&&nx==ex&&now.turns+<=k)
{
printf("yes\n");
return ;
}
}
ny+=dy[i];
nx+=dx[i];
}
}
} printf("no\n");
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
memset(vis,,sizeof(vis));
scanf("%d %d",&m,&n);
scanf("%*c");
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
scanf("%c",&g[i][j]);
}
scanf("%*c");
}
scanf("%d %d %d %d %d",&k,&sx,&sy,&ex,&ey);
bfs();
} return ;
}
最新文章
- 深度解析C语言int与unsigned int
- angularJS: shop chart
- OC-id、构造方法
- json学习系列(2)-生成JSONObject的方法
- 深入理解javacript之prototype
- Windows Server 2003 IIS支持ASP
- Sina App Engine(SAE)入门教程(9)- SaeMail(邮件)使用
- Android 在webView中创建web应用(译文)
- 怎样查询SCI和EI检索号
- 让ASP.NET Core支持GraphQL之-GraphQL的实现原理
- 网络传输数据序列化工具Protostuff
- 第一节,初识OpenCV3-图像的读、写、显、格式转化等
- [DUBBO] Unexpected error occur at send statistic, cause: Forbid consumer 192.168.3.151 access servic
- 2017CS231n学习笔记——计算机视觉的概述
- ANSYS - 修改节点荷载的规则
- Web接口测试-HttpClient
- web----Tornado
- python 读csv格式的文件
- computer、methods和watch
- 使用ab对网站进行压力测试