用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 ;
}

最新文章

  1. 深度解析C语言int与unsigned int
  2. angularJS: shop chart
  3. OC-id、构造方法
  4. json学习系列(2)-生成JSONObject的方法
  5. 深入理解javacript之prototype
  6. Windows Server 2003 IIS支持ASP
  7. Sina App Engine(SAE)入门教程(9)- SaeMail(邮件)使用
  8. Android 在webView中创建web应用(译文)
  9. 怎样查询SCI和EI检索号
  10. 让ASP.NET Core支持GraphQL之-GraphQL的实现原理
  11. 网络传输数据序列化工具Protostuff
  12. 第一节,初识OpenCV3-图像的读、写、显、格式转化等
  13. [DUBBO] Unexpected error occur at send statistic, cause: Forbid consumer 192.168.3.151 access servic
  14. 2017CS231n学习笔记——计算机视觉的概述
  15. ANSYS - 修改节点荷载的规则
  16. Web接口测试-HttpClient
  17. web----Tornado
  18. python 读csv格式的文件
  19. computer、methods和watch
  20. 使用ab对网站进行压力测试

热门文章

  1. php自定义函数: amr转mp3格式
  2. Android笔记之WebView加载网页的进度回调
  3. PAT 1052. 卖个萌 (20)
  4. 好用的 curl 抓取 页面的封装函数
  5. Python中PIL及Opencv转化
  6. crontab定时任务写法记录
  7. linux 11 -- mount,umount
  8. QT里面的delay使用
  9. MOOC 数据结构 01-复杂度3 二分查找
  10. LRC歌词文件读取代码