题目链接:http://poj.org/problem?id=3083

解题报告:这个题目,搜最短路,没有什么问题。优先走左边,走右边,有很多说法,思路大概都相同,都是记录当前朝向,根据数学公式(i+j+3)%4计算下一个方向,但是小草发现有些博客里面有一点点小错误,就是在方向的表示上。

左边优先,上右下左分别为0、1、2、4。dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

右边优先,左下右上分别为0、1、2、3。dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue> using namespace std; #define MAXN 1000000007
#define judge(x,y) x>=0&&x<m&&y>=0&&y<n&&map[x][y]!='#'&&!vis[x][y] int dir1[][]= {{-,},{,},{,},{,-}}; ///左边优先
int dir2[][]= {{,-},{,},{,},{-,}}; ///右边优先 char map[][];
bool vis[][]; int m,n; struct node
{
int x,y;
int dist;
}; int step,START_I;
int left_step=,right_step=; int DFS(int x,int y,int I,int di[][])
{
if(map[x][y]=='E') return ;
int i,j;
for(j=; j<; j++)
{
i=(I+j+)%;
if(judge(x+di[i][],y+di[i][]))
{
step=DFS(x+di[i][],y+di[i][],i,di)+;
break;
}
}
return step;
} int bfs(int x,int y)
{
memset(vis,,sizeof(vis));
queue<node> q;
node u;
u.x=x;
u.y=y;
u.dist=;
vis[u.x][u.y]=true;
q.push(u);
while(!q.empty())
{
u=q.front();
int d=u.dist;
if(map[u.x][u.y]=='E')
return u.dist;
q.pop();
for(int i=; i<; i++)
{
node v;
v.x=u.x+dir1[i][];
v.y=u.y+dir1[i][];
if(judge(v.x,v.y))
{
vis[v.x][v.y]=true;
v.dist=d+;
q.push(v);
}
}
}
return ;
} int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
memset(map,,sizeof(map));
memset(vis,,sizeof(vis)); scanf("%d%d",&n,&m);
int sx,sy; ///开始的坐标 for(int i=; i<m; i++)
{
scanf("%s",map[i]);
for(int j=; j<n; j++)
if(map[i][j]=='S') sx=i,sy=j;
} ///一直向左走时,先找到出口的方向
for(int i=; i<; i++)
if(judge(sx+dir1[i][],sy+dir1[i][])) ///从这个点搜四边,是否有出口,并且记录下来出口,上右下左分别为0,1,2,3,
START_I=i; ///(i+j+3)%4
step=;
left_step=DFS(sx,sy,START_I,dir1); ///向右
for(int i=; i<; i++)
if(judge(sx+dir2[i][],sy+dir2[i][])) ///从这个点搜四边,是否有出口,并且记录下来出口,左下右上分别为0,1,2,3,
START_I=i; ///(i+j+3)%4
step=;
memset(vis,,sizeof(vis));
right_step=DFS(sx,sy,START_I,dir2);
printf("%d %d %d\n",left_step,right_step,bfs(sx,sy)+);
}
return ;
}

最新文章

  1. Atitit 图像金字塔原理与概率 attilax的理解总结qb23
  2. JAVA通过poi对Excel数据在(jsp+ssh)环境下导入导出
  3. 利用 Postfix 抵擋垃圾信
  4. 选择第n小的元素之python实现源码
  5. php的ob实现页面静态化
  6. Y - Design T-Shirt(第二季水)
  7. 六、Solr高亮与Field权重
  8. L8_2
  9. 【C语言】字符串模块
  10. validateform正则表达式 datatype验证数字
  11. eclipse里index.jsp头部报错的原因和解决方法
  12. CCF系列之画图(201409-2)
  13. MySQL 使用自增ID主键和UUID 作为主键的优劣比较详细过程(从百万到千万表记录测试)
  14. Gym101889J. Jumping frog(合数分解+环形dp预处理)
  15. [转]ConcurrentHashMap原理分析
  16. 记一次包含iframe的需要滚动的元素不能滚动到底部的问题
  17. 从零开始写bootloader(2)
  18. vue中的插槽slot
  19. HDU 4778 Gems Fight! (2013杭州赛区1009题,状态压缩,博弈)
  20. 【jmeter】jmeter环境搭建

热门文章

  1. NPOI2.0导出excel之添加样式、边框和表头
  2. java中所有开源注解收集
  3. es6数组新方法
  4. stream2
  5. Mybatis学习笔记8 - resultMap自定义结果集映射规则
  6. 搜索提示(search suggest)文献阅读
  7. 判断元素类型JS
  8. svn使用&amp;&amp;常用操作&amp;&amp;问题处理
  9. 【补充】docker基础学习
  10. JavaSE之Java基础(1)