POJ 3083 -- Children of the Candy Corn(DFS+BFS)TLE

时间:2022-09-07 08:09:08

POJ 3083 -- Children of the Candy Corn(DFS+BFS)

题意:

给定一个迷宫,S是起点,E是终点,#是墙不可走,.可以走

1)先输出左转优先时,从S到E的步数

2)再输出右转优先时,从S到E的步数

3)最后输出S到E的最短步数

解题思路:

前两问DFS,转向只要控制一下旋转方向就可以

首先设置前进方向对应的数字

向上——N——0

向右——E——1

向下——S——2

向左——W——3

比如说右转优先,即为向右,向前,向左,向后,即逆时针方向for(int i=1;i>=-2;i--)

左转优先,即为向左,向前,向右,向后,即顺时针方向for(int i=-1;i<=3;i++)

第三问最短路,BFS

普通递归(TLE)

 #include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int r,c;///行r,列c
int r0,c0,r3,c3;///r0,c0用来标记入口,r3,c3用来标记出口
const char *dirs = "NESW";
const int maxn = ;
char square[maxn][maxn];
const int dr[] = {-,,,};
const int dc[] = { ,,,-};
struct node{
int row,col,deep;
int dir;///0123对应NESW
node(int row=,int col=,int dir=,int deep=):row(row),col(col),dir(dir),deep(deep){}
};
bool inside(int xx,int yy)
{
return xx>= && xx<=r && yy>= && yy<=c;
} bool flag1;
int step1;
void dfs1(node *way,int x,int y,int d,int step)
{///左转优先
way[step].row = x;
way[step].col = y;
way[step].dir = d;
if(x==r3 && y==c3)///走到出口
{
step1 = step;
flag1 = true;
return;
}
for(int i=-;i<=;i++)
{
int tempDir = (way[step].dir + + i)%;///进行旋转
int xx = way[step].row + dr[tempDir];
int yy = way[step].col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界,可以行走
dfs1(way,xx,yy,tempDir,step+);
}
if(flag1)
return;
}
return;
} int step2;bool flag2;
void dfs2(node *way,int x,int y,int d,int step)
{///右转优先
way[step].row = x;
way[step].col = y;
way[step].dir = d;
if(x==r3 && y==c3)///走到出口
{
step2 = step;
flag2 = true;
return;
}
for(int i=;i>=-;i--)
{
int tempDir = (way[step].dir + + i)%;///进行旋转
int xx = way[step].row + dr[tempDir];
int yy = way[step].col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界,可以行走
dfs2(way,xx,yy,tempDir,step+);
}
if(flag2)
return;
}
return;
}
node d[maxn][maxn][]; void bfs(int x,int y,int d)
{
queue<node> q;
node u(x,y,d,);///入口结点
q.push(u);
while(!q.empty())
{
node u = q.front();q.pop();
if(u.row == r3 && u.col == c3)
{
cout<<u.deep<<endl;
return;
}
for(int i=;i<=;i++)
{
int tempDir = (u.dir +i)%;///进行旋转
int xx = u.row + dr[tempDir];
int yy = u.col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界,可以行走
node v(xx,yy,tempDir,u.deep+);
q.push(v);
}
}
}
} int startDir()
{///计算从入口进入之后的方向
if(r0 == ) return ;
else if(r0 == r) return ;
else if(c0 == ) return ;
else return ;
}
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>c>>r;///输入为先输入列数,在输入行数
char temp;
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
{
temp = getchar();
while(temp == '\n') temp = getchar();
square[i][j] = temp;
if(temp == 'S'){r0 = i;c0 = j;}
if(temp == 'E'){r3 = i;c3 = j;}
}
node *way = new node[maxn*maxn];
///求解左转优先
flag1 = false;step1 = ;
int startdir = startDir();
dfs1(way,r0,c0,startdir,);
if(flag1) cout<<step1<<" ";
///求解右转优先
flag2 = false;step2 = ;
dfs2(way,r0,c0,startdir,);
if(flag2) cout<<step2<<" ";
///求解最短路径
bfs(r0,c0,startdir);
}
return ;
}

POJ 3083 -- Children of the Candy Corn(DFS+BFS)TLE

POJ 3083 -- Children of the Candy Corn(DFS+BFS)TLE

 最终成功代码

Time Limit Exceeded原因:POJ对STL兼容性不高,使用queue超时

其次,DFS使用尾递归形式,遇到可行解,直接向下一层搜索

最后,BFS不能走重复路线,否则会陷入死循环,Runtime Error

仅此告诫自己

 #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int r,c;///行r,列c
int r0,c0,r3,c3;///r0,c0用来标记入口,r3,c3用来标记出口 const int maxn = ;
char square[maxn][maxn];
const int dr[] = {-,,,};
const int dc[] = { ,,,-}; struct node{
int row,col,deep;
int dir;///0123对应NESW
node(int row=,int col=,int dir=,int deep=):row(row),col(col),dir(dir),deep(deep){}
};
bool inside(int xx,int yy)
{
return xx>= && xx<=r && yy>= && yy<=c;
}
int dfs12(int x,int y,int d)
{///左转优先
if(square[x][y] == 'E')
return ;
int tempDir,xx,yy;
for(int i=-;i<=;i++)
{
tempDir = (d + + i)%;///进行旋转
xx = x + dr[tempDir];
yy = y + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界,可以行走
break;
}
}
return dfs12(xx,yy,tempDir)+;
}
int dfs22(int x,int y,int d)
{///you转优先
if(square[x][y] == 'E')
return ;
int tempDir,xx,yy; for(int i=;i>=-;i--)
{
tempDir = (d + + i)%;///进行旋转
xx = x + dr[tempDir];
yy = y + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界,可以行走
break;
}
}
return dfs22(xx,yy,tempDir)+;
} node queue[];
bool has_walk[maxn][maxn];
void bfs(int x,int y,int d)
{
int head=,tail=;
node u(x,y,d,);
has_walk[x][y] = false;
queue[head] = u;///入口结点
while(head<tail)
{
node u = queue[head++];
if(u.row == r3 && u.col == c3)
{
cout<<u.deep<<endl;
return;
}
for(int i=;i<=;i++)
{
int tempDir = (u.dir +i)%;///进行旋转
int xx = u.row + dr[tempDir];
int yy = u.col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#' && has_walk[xx][yy])
{///没有出界,可以行走,没有走过true
node v(xx,yy,tempDir,u.deep+);
has_walk[xx][yy] = false;
queue[tail] = v;
tail++;
}
}
}
} int startDir()
{///计算从入口进入之后的方向
if(r0 == ) return ;
else if(r0 == r) return ;
else if(c0 == ) return ;
else return ;
}
int main()
{
int n;
while(cin>>n)
while(n--)
{
cin>>c>>r;///输入为先输入列数,在输入行数
memset(has_walk,true,sizeof(has_walk));///true表示当前格子没有走过,可以走
char temp;
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
{
temp = getchar();
while(temp == '\n') temp = getchar();
square[i][j] = temp;
if(temp == 'S'){r0 = i;c0 = j;}
if(temp == 'E'){r3 = i;c3 = j;}
}
///求解左转优先
int startdir = startDir();
cout<<dfs12(r0,c0,startdir)<<" ";
///求解右转优先
cout<<dfs22(r0,c0,startdir)<<" ";
///求解最短路径
bfs(r0,c0,startdir);
}
return ;
}

POJ 3083 -- Children of the Candy Corn(DFS+BFS)TLE

最后给大家提供点测试样例:


########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E#### #########
#.#.#.#.#
S.......E
#.#.#.#.#
######### ########
#.#.#..#
S......E
#.#.#..#
######## ##
SE
## ######E#
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S######
结果:

POJ 3083 -- Children of the Candy Corn(DFS+BFS)TLE的更多相关文章

  1. poj 3083 Children of the Candy Corn(DFS&plus;BFS)

    做了1天,总是各种错误,很无语 最后还是参考大神的方法 题目:http://poj.org/problem?id=3083 题意:从s到e找分别按照左侧优先和右侧优先的最短路径,和实际的最短路径 DF ...

  2. POJ 3083:Children of the Candy Corn(DFS&plus;BFS)

    Children of the Candy Corn Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9311 Accepted: ...

  3. poj 3083 Children of the Candy Corn (广搜,模拟,简单)

    题目 靠墙走用 模拟,我写的是靠左走,因为靠右走相当于 靠左走从终点走到起点. 最短路径 用bfs. #define _CRT_SECURE_NO_WARNINGS #include<stdio ...

  4. poj 3083 Children of the Candy Corn

    点击打开链接 Children of the Candy Corn Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8288 ...

  5. POJ 3083 Children of the Candy Corn bfs和dfs

      Children of the Candy Corn Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8102   Acc ...

  6. POJ&colon;3083 Children of the Candy Corn&lpar;bfs&plus;dfs&rpar;

    http://poj.org/problem?id=3083 Description The cornfield maze is a popular Halloween treat. Visitors ...

  7. POJ 3083 Children of the Candy Corn &lpar;DFS &plus; BFS&rpar;

    POJ-3083 题意: 给一个h*w的地图. '#'表示墙: '.'表示空地: 'S'表示起点: 'E'表示终点: 1)在地图中仅有一个'S'和一个'E',他们为位于地图的边墙,不在墙角: 2)地图 ...

  8. POJ 3083 Children of the Candy Corn &lpar;DFS &plus; BFS &plus; 模拟&rpar;

    题目链接:http://poj.org/problem?id=3083 题意: 这里有一个w * h的迷宫,给你入口和出口,让你分别求以下三种情况时,到达出口的步数(总步数包括入口和出口): 第一种: ...

  9. poj 3083 Children of the Candy Corn 【条件约束dfs搜索 &plus; bfs搜索】【复习搜索题目一定要看这道题目】

    题目地址:http://poj.org/problem?id=3083 Sample Input 2 8 8 ######## #......# #.####.# #.####.# #.####.# ...

随机推荐

  1. jq 移除包含某个字符串的类名js

    el.removeClass (function (index, css) { return (css.match (/(^|\s)star\S+/g) || []).join(' ');//移除以“ ...

  2. exports 和 module&period;exports 的区别

    https://cnodejs.org/topic/5231a630101e574521e45ef8 //一句话总结:exports是对module.exports的引用,require()返回的是 ...

  3. Android SDK Manager Google Apis 下载

    本意是想利用google的gcm来实装android推送功能的,很遗憾, google貌似已经停止提供啥服务给国内了,或者说国内想继续使用google 服务暂时变得几乎不可能了.找了个代理来进行goo ...

  4. 【BZOJ】【3504】【CQOI2014】危桥

    网络流/最大流 比较裸的最大流= = 无向图上走来回其实就等价与走两遍>_> 如果路径有相交其实不影响答案的 比较恶心的是两个人路过同一座桥,但走的方向不同互相抵消流量了…… 其实只要在第 ...

  5. 自定义的IntentFileter 无法找到activity

    <intent-filter > <action android:name="com.leo.enjoytime.VIEW"/></intent-fi ...

  6. win7下的iis配置

    1.配置错误 说明:在处理向该请求提供服务所需的配置文件时出错.请检查下面的特定错误详细信息并适当地修改配置文件. 分析器错误消息:无法识别的属性“targetFramework”.请注意属性名称区分 ...

  7. VC &plus;&plus; 后台消息模拟

    —HWND TO=; —//TO=::FindWindow(_T("Chrome_RenderWidgetHostHWND"),NULL); —TO=::FindWindow(_T ...

  8. oracle&lowbar;修改连接数

    修改Oracle最大连接数 1.查询Oracle会话的方法   select * from v$session 2.修改Oracle最大连接数的方法      a.以sysdba身份登陆PL/SQL ...

  9. Linq 等式运算符:SequenceEqual

    检查元素的数量,每个元素的值及两个集合中元素的顺序是否相等,3个方面都相等则为true,否则为false IList<string> strList1 = new List<stri ...

  10. 校内模拟赛 旅行&lpar;by NiroBC&rpar;

    题意: n个点的无向图,Q次操作,每次操作可以连接增加一条边,询问两个点之间有多少条边是必经之路.如果不连通,输出-1. 分析: 首先并查集维护连通性,每次加入一条边后,如果这条边将会连接两个联通块, ...