hdu 1728

//hdu 1728

//这个是一道很经典的迷宫题了,思路感觉。。。取起点和终点,判断连线是否超过n个弯,

//先是从起点出发,上下左右四个方向搜索,找到一条路,把那条路的第一个点压入队列

//然后沿着那个方向一直搜下去,直到不符合条件(4个方向都动不了),就从队列里面去首元素

//然后不断循环这个操作。。。。

#include <iostream>
#include <cstring>
#include <queue>
#include <stdio.h>
#include <algorithm>
using namespace std; char Map[110][110];
int vis[110][110];
int dx[]={0,0,-1,1};//两个数组是搜索的时候用
int dy[]={-1,1,0,0}; int k,x1,x2,y1,y2,i,side1,side2;
struct dot
{
int x,y,k;//k存放转弯数
}; void BFS(dot a,dot b)
{
int flag=0; vis[a.x][a.y]=1;//flag标记是否到达目标
dot m,n; m.x=a.x; m.y=a.y; m.k=-1;//m,n为中间变量
queue<dot>q; q.push(m);//将起点a(m)入队列
while(!q.empty())//别问为什么要用队列非空来做。。。书上写的,记住就ok,因为你还不是大牛
{
m=q.front();
q.pop(); if(m.x==b.x&&m.y==b.y&&m.k<=k) {flag=1; break;} n.k=m.k+1;//因为每次从队列取出首元素,这个时候已经增加了一个弯 for(i=0;i<4;i++)//开始搜索
{
int j=m.x+dx[i];
int l=m.y+dy[i];
while(j>=0&&j<side1&&l>=0&&l<side2&&Map[j][l]!='*')//判断条件
{
if(!vis[j][l])
{
vis[j][l]=1;
n.x=j;
n.y=l;
q.push(n);//如果没被标记,那么标记它,用n记下此时坐标值,压入队列中
}
j+=dx[i];//朝某个方向一直搜索
l+=dy[i];
}
}
}
if(flag==1) cout<<"yes\n";
else
cout<<"no\n";
} int main()
{
int t;
cin>>t;
while(t--)
{
memset(vis,0,sizeof(vis));
//memset(Map,0,sizeof(Map));
dot _m,_n;
cin>>side1>>side2;
for(i=0;i<side1;i++)
cin>>Map[i];
cin>>k>>y1>>x1>>y2>>x2;//要注意这个地方好坑人。。。。。
_m.x=x1-1; _m.y=y1-1;
_n.x=x2-1; _n.y=y2-1;
BFS(_m,_n);
}
return 0;
}
上一篇:【windows 下安装 mysql-server 无法登录问题解决】


下一篇:Linux下针对路由功能配置iptables的方法详解