文档章节

简单版贪吃蛇(广搜+保存路径)(广搜保存路径 超时)

1
 1944864971
发布于 2016/07/24 11:59
字数 656
阅读 6
收藏 0

/*
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3128

心得技巧:
此题用数组模拟对列 因为这样出对后队列里面的数据仍然保存着便于后来查找父节点
若是用stl的模板出队后队列的数据都删除了;不容易查找父节点;

*/

include

include

include

include

using namespace std;
char map1[4]= {'E','S','W','N'};//映射方向
char miGong[105][105];
int vis[105][105];
int dir[4][2]= {0,1,1,0,0,-1,-1,0};
int m,n;
struct note
{
int x;
int y;
int faX;//记录方向
int fu;//记录父节点
} q[105*105];
bool bfs(int sx,int sy,int ex,int ey,int &bN)
{
int head=1;
int tail=1;
q[tail].x=sx;
q[tail].y=sy;
tail++;
vis[sx][sy]=1;
while(head<tail)
{
if(q[head].x==ex&&q[head].y==ey)
{
bN=head;
return true;
}
for(int i=0; i<4; i++)
{
int tx=q[head].x+dir[i][0];
int ty=q[head].y+dir[i][1];
if(tx<0||ty<0||tx>=m||ty>=n)
continue;
if(miGong[tx][ty]!='#'&&vis[tx][ty]==0)
{
vis[tx][ty]=1;
q[tail].x=tx;
q[tail].y=ty;
q[tail].fu=head;//保存父节点
q[tail].faX=i;//保存方向
tail++;
}
}
head++;
}
return false;
}
void out(int x)
{
if(x==1)//第一个节点 即是入口
return;//退回上一步调用函数的的位置
out(q[x].fu);
printf("%c",map1[q[x].faX]);//输出方向
}
int main()

{
while(~scanf("%d%d",&m,&n))
{
memset(miGong,'#',sizeof(miGong));
memset(vis,0,sizeof(vis));
int sx,sy,ex,ey;
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
{
scanf(" %c",&miGong[i][j]);
if(miGong[i][j]=='S')
{
sx=i;
sy=j;
}
if(miGong[i][j]=='E')
{
ex=i;
ey=j;
}
}
int bN;
if( bfs(sx,sy,ex,ey,bN))
{
out(bN);
printf("\n");
}
else printf("Can't eat it!\n");
}
return 0;
}

/*
5 5
.....
.....

.

ES...

5 5
....S
.....

.

E....

*/

/*

深搜

*/

include

include

include

include

using namespace std;
char map1[4]= {'E','S','W','N'};
char miGong[105][105];
int vis[105][105];
int dir[4][2]= {0,1,1,0,0,-1,-1,0};
int m,n,cur=0,min1=999999;
int sx,sy,ex,ey;
int a[105*105];
int b[105*105],k,k1;
void dfs(int x,int y,int s)
{
if(x==ex&&y==ey)
{
cur=1;
if(s<min1)
{
min1=s;
for(int i=0; i<k; i++)//把最优的路径保存下来
b[i]=a[i];
k1=k;
k=0;
}
return ;
}
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(tx<0||ty<0||tx>=m||ty>=n)
continue;
if(miGong[tx][ty]!='#'&&vis[tx][ty]==0)
{
vis[tx][ty]=1;
a[k++]=i;
dfs(tx,ty,s+1);
k--;//每退回一次 出栈一次
vis[tx][ty]=0;
}
}
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
memset(miGong,'#',sizeof(miGong));
memset(vis,0,sizeof(vis));
min1=9999;
k=k1=0;
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
{
scanf(" %c",&miGong[i][j]);
if(miGong[i][j]=='S')
{
sx=i;
sy=j;
}
if(miGong[i][j]=='E')
{
ex=i;
ey=j;
}
}
dfs(sx,sy,0);
if(cur==1)
{
for(int i=0;i<k1;i++)
printf("%c",map1[b[i]]);
printf("\n");
}
else printf("Can't eat it!\n");
}
return 0;
}

本文转载自:http://www.cnblogs.com/aaaadengchaochao/p/5318991.html

1
粉丝 0
博文 57
码字总数 0
作品 0
郑州
私信 提问
深搜和广搜--原理彼此的优缺点

转自http://www.cnblogs.com/A-FM/p/5240887.html 一般来说,广搜常用于找单一的最短路线,或者是规模小的路径搜索,它的特点是"搜到就是最优解", 而深搜用于找多个解或者是"步数已知(好比...

Dear_Jia
2017/11/16
0
0
FZU ~ 2150 ~ Fire Game (双点BFS)

题意:你最多可以选择两处火源,要把整个地图上的草地都点燃,火可以往上下左右四个方向扩散,能否把所有的草地都点燃,能的话输出最少时间,不能输出-1;'#'代表草地,'.'表示空地,空地不会...

ZscDst
2017/12/25
0
0
面试算法:图

 并查集  图的存储  深度优先搜索 老鼠吃奶酪问题 百数问题  最短路径 Dijkstra 启发式搜索:A*算法 Floyd/Bellman-Ford  最小生成树 (MST) Prim/Krusal 深/广搜 http://my.oschin...

datacube
2016/07/26
9
0
如何用编程 get 百万年终奖?

2018 年 CSDN 软件开发者大调查活动开始了!自 2004 年开始,我们通过对开发人员、开发技术以及开发工具、平台的状况和发展趋势等进行深入的调研,为开发者呈现了一幅幅真实的中国开发者画像...

CSDN资讯
2018/11/04
0
0
关于微信支付退款CURL错误号52 与 商户后台退款提示证书无效的解决方案

大家好,刚才写的文档用的在线云存储,谢了一大堆,保存成功了,但是我再次打开显示无法打开文件,我去,所以别用word.baidu.com这个东西了,有点可恨。 在微信开发中各位难免会被遇到各种各...

sizeof
2015/05/05
840
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
198
4
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
10
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部