HDU 1728题逃离迷宫
【摘要】 题目链接~~>
这题开始时以为是简单的搜索题，错了好几次，上网上参考了一下，才恍然大悟，搜一个方向要一直搜到底，或者让一些点重新入队，实现再次搜索，这样写完后还是wa，又重新看了一下代码，写错了一个字符。
参考代码：
#include<stdio.h>#include<qu...
这题开始时以为是简单的搜索题，错了好几次，上网上参考了一下，才恍然大悟，搜一个方向要一直搜到底，或者让一些点重新入队，实现再次搜索，这样写完后还是wa，又重新看了一下代码，写错了一个字符。
参考代码：
-
#include<stdio.h>
-
#include<queue>
-
using namespace std;
-
int n,m,k;
-
char s[105][105];
-
int vis[105][105],dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
-
struct zhang
-
{
-
int x,y,bu,d;
-
};
-
bool diy(int x,int y)
-
{
-
if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.')
-
return true ;
-
else return false ;
-
}
-
void bfs(int x1,int y1)
-
{
-
int i;
-
queue<zhang>q;
-
zhang current,next;
-
for(i=0;i<4;i++)
-
{
-
current.x=x1+dx[i];
-
current.y=y1+dy[i];
-
current.bu=0;
-
current.d=i;
-
if(diy(current.x,current.y))
-
{
-
vis[current.x][current.y]=0;
-
q.push(current);
-
}
-
}
-
while(!q.empty())
-
{
-
current=q.front();
-
q.pop();
-
for(i=0;i<4;i++)
-
{
-
next.x=current.x+dx[i];
-
next.y=current.y+dy[i];
-
if(current.d!=i)
-
next.bu=current.bu+1;
-
else next.bu=current.bu;
-
next.d=i;
-
if(next.bu<=k&&diy(next.x,next.y))
-
{
-
if(next.bu<=vis[next.x][next.y])//很重要！如果步数相等则再次入队，
-
{ //等于又在另一个方向上进行
-
vis[next.x][next.y]=next.bu;
-
q.push(next);
-
}
-
}
-
}
-
}
-
}
-
int main()
-
{
-
int T,i,y1,x1,x2,y2;
-
scanf("%d",&T);
-
while(T--)
-
{
-
scanf("%d%d",&n,&m);
-
for(i=0;i<n;i++)
-
scanf("%s",s[i]);
-
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
-
y1--;x1--;y2--;x2--;
-
for(i=0;i<n;i++)
-
for(int j=0;j<m;j++)
-
vis[i][j]=20;
-
bfs(x1,y1);
-
if(vis[x2][y2]<=k)
-
printf("yes\n");
-
else printf("no\n");
-
}
-
return 0 ;
-
}
源代码：
-
#include<stdio.h>
-
#include<queue>
-
using namespace std;
-
int vis[150][150];
-
char s[150][150];
-
int n,m,k,y2,x2;
-
struct zhang
-
{
-
int x,y,bu,d;
-
};
-
void bfs(int x1,int y1)
-
{
-
int i;
-
zhang current,next;
-
queue<zhang>q;
-
current.x=x1;
-
current.y=y1;
-
current.bu=0;
-
current.d=-1;
-
vis[current.x][current.y]=-1;
-
q.push(current);
-
while(!q.empty())
-
{
-
current=q.front();
-
q.pop();
-
if(current.d==-1)//刚开始搜索时
-
{
-
for(i=current.y+1;i<m;i++)//右 1
-
if(s[current.x][i]!='*')
-
{
-
next.d=1;
-
next.x=current.x;
-
next.y=i;
-
next.bu=0;
-
vis[next.x][next.y]=0;
-
q.push(next);
-
}
-
else break;
-
for(i=current.y-1;i>=0;i--)// 左 2
-
if(s[current.x][i]!='*')
-
{
-
next.d=2;
-
next.x=current.x;
-
next.y=i;
-
next.bu=0;
-
vis[next.x][next.y]=0;
-
q.push(next);
-
}
-
else break;
-
for(i=current.x-1;i>=0;i--)// 上 3
-
if(s[i][current.y]!='*')
-
{
-
next.d=3;
-
next.y=current.y;
-
next.x=i;
-
next.bu=0;
-
vis[next.x][next.y]=0;
-
q.push(next);
-
}
-
else break;
-
for(i=current.y+1;i<n;i++)// 下 4
-
if(s[i][current.y]!='*')
-
{
-
next.d=4;
-
next.y=current.y;
-
next.x=i;
-
next.bu=0;
-
vis[next.x][next.y]=0;
-
q.push(next);
-
}
-
else break;
-
}
-
else {//沿着四个方向一直搜到底
-
for(i=current.y+1;i<m;i++)// 右 1
-
if(s[current.x][i]!='*')
-
{
-
if(current.d!=1)
-
next.bu=current.bu+1;
-
else
-
next.bu=current.bu;
-
-
if(next.bu<vis[current.x][i])
-
{
-
vis[current.x][i]=next.bu;
-
next.d=1;
-
next.x=current.x;
-
next.y=i;
-
q.push(next);
-
}
-
}
-
else break;
-
for(i=current.y-1;i>=0;i--)// 左 2
-
if(s[current.x][i]!='*')
-
{
-
if(current.d!=2)
-
next.bu=current.bu+1;
-
else
-
next.bu=current.bu;
-
if(next.bu<vis[current.x][i])
-
{
-
vis[current.x][i]=next.bu;
-
next.d=2;
-
next.x=current.x;
-
next.y=i;
-
q.push(next);
-
}
-
}
-
else break;
-
for(i=current.x-1;i>=0;i--)// 上 3
-
if(s[i][current.y]!='*')
-
{
-
if(current.d!=3)
-
next.bu=current.bu+1;
-
else
-
next.bu=current.bu;
-
if(next.bu<vis[i][current.y])
-
{
-
vis[i][current.y]=next.bu;
-
next.d=3;
-
next.x=i;
-
next.y=current.y;
-
q.push(next);
-
}
-
}
-
else break;
-
for(i=current.x+1;i<n;i++)// 下 4
-
if(s[i][current.y]!='*')
-
{
-
if(current.d!=4)
-
next.bu=current.bu+1;
-
else
-
next.bu=current.bu;
-
if(next.bu<vis[i][current.y])
-
{
-
vis[i][current.y]=next.bu;
-
next.d=4;
-
next.x=i;
-
next.y=current.y;
-
q.push(next);
-
}
-
}
-
else break;
-
}
-
}
-
}
-
int main()
-
{
-
int T,x1,y1;
-
scanf("%d",&T);
-
while(T--)
-
{
-
scanf("%d%d",&n,&m);
-
for(int i=0;i<n;i++)
-
scanf("%s",s[i]);
-
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
-
y2--; x2--;
-
for(int i=0;i<n;i++)
-
for(int j=0;j<m;j++)
-
vis[i][j]=20;
-
bfs(x1-1,y1-1);
-
if(vis[x2][y2]<=k)
-
printf("yes\n");
-
else
-
printf("no\n");
-
}
-
return 0;
-
}
-
//必须全部搜完有一些点的拐弯次数不断在更新
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/11030537
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）