Children of the Candy Corn (bfs+dfs)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8120 | Accepted: 3547 |
Description
One popular maze-walking strategy guarantees that the visitor will eventually find the exit. Simply choose either the right or left wall, and follow it. Of course, there's no guarantee which strategy (left or right) will be better, and the path taken is seldom the most efficient. (It also doesn't work on mazes with exits that are not on the edge; those types of mazes are not represented in this problem.)
As the proprieter of a cornfield that is about to be converted into a maze, you'd like to have a computer program that can determine the left and right-hand paths along with the shortest path so that you can figure out which layout has the best chance of confounding visitors.
Input
Exactly one 'S' and one 'E' will be present in the maze, and they will always be located along one of the maze edges and never in a corner. The maze will be fully enclosed by walls ('#'), with the only openings being the 'S' and 'E'. The 'S' and 'E' will also be separated by at least one wall ('#').
You may assume that the maze exit is always reachable from the start point.
Output
Sample Input
2
8 8
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E####
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########
Sample Output
37 5 5
17 17 9
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std; struct node
{
int x,y;
int step;
};
int n,m;
char map[][];
int vis[][];
int dir[][] = {{-,},{,-},{,},{,}};//上左下右顺时针;
queue <node> que;
int ans3; int dfs(int sx,int sy, int ex, int ey, int d, int ans)
{
if(sx == ex && sy == ey)
return ans;
d = (d+)%;//左转;
while(map[sx+dir[d][]][sy+dir[d][]] == '#')
d = (d+)%;//当有墙的时候就右转直到没有墙;
return dfs(sx+dir[d][],sy+dir[d][],ex,ey,d,ans+);
} void bfs(int sx,int sy, int ex, int ey)
{
while(!que.empty())
que.pop();
memset(vis,,sizeof(vis)); que.push((struct node){sx,sy,});
vis[sx][sy] = ; while(!que.empty())
{
struct node u = que.front();
que.pop();
if(u.x == ex && u.y == ey)
{
ans3 = u.step;
return;
}
if(u.x- >= && !vis[u.x-][u.y] && map[u.x-][u.y] != '#')
{
vis[u.x-][u.y] = ;
que.push((struct node){u.x-,u.y,u.step+});
}
if(u.x+ <= n && !vis[u.x+][u.y] && map[u.x+][u.y] != '#')
{
vis[u.x+][u.y] = ;
que.push((struct node){u.x+,u.y,u.step+});
}
if(u.y- >= && !vis[u.x][u.y-] && map[u.x][u.y-] != '#')
{
vis[u.x][u.y-] = ;
que.push((struct node){u.x,u.y-,u.step+});
}
if(u.y+ <= m && !vis[u.x][u.y+] && map[u.x][u.y+] != '#')
{
vis[u.x][u.y+] = ;
que.push((struct node){u.x,u.y+,u.step+});
}
}
}
int main()
{
int t;
int sx,sy,ex,ey;
scanf("%d",&t);
while(t--)
{
memset(map,'#',sizeof(map));//外面加一道墙,从s进去之后只有一条路可走;
scanf("%d %d",&m,&n);
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
cin>>map[i][j];
if(map[i][j] == 'S')
{
sx = i;
sy= j;
}
if(map[i][j] == 'E')
{
ex = i;
ey = j;
}
}
}
printf("%d %d ",dfs(sx,sy,ex,ey,,),dfs(ex,ey,sx,sy,,));
bfs(sx,sy,ex,ey);
printf("%d\n",ans3);
}
return ;
}
最新文章
- 2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest
- 【转】aspx与aspx.cs的关系
- Objective-C 利用OC的消息机制,使用Method Swizzling进行方法修改
- input上传按钮 文字修改办法
- 解决hibernate向mysql插入中文乱码问题
- Windows 10正式版官方原版ISO镜像下载
- NSFileManager文件管理
- Codeforces Round #226 (Div. 2)A. Bear and Raspberry
- 【HDOJ】2389 Rain on your Parade
- source code of MES Data
- Dollar Dayz poj3181
- MSIL实用指南-加载bool、sbyte、byte、char、short等值
- (NO.00004)iOS实现打砖块游戏(八):游戏中小球与砖块的碰撞
- Android开发工具下载地址
- 遗传算法解决TSP问题实现以及与最小生成树的对比
- c# MD5及盐值加密
- python小总结3(异常、单例设计模式)
- NMON使用以及nmon_analyse生成分析报表
- 【推荐】Hutool 的通用工具类库
- ADO.NET的五大对象【转】