http://poj.org/problem?id=3009

题意 : 迷宫升级版,也是m*n的迷宫,0是可以走的,1是阻塞,2是初始点,3是目标位置,这个的阻塞是可以消除的,就是说只要石头撞到阻塞,阻塞就由1变为0了,石头这个时候是可以停下来的,也就是说石头只有撞上阻塞停下来才算走了一步,还有要注意的一点是石头停了下来的时候不是停在阻塞那个点那的,还是它撞阻塞之前的那个位置,求出走到目标位置需要的步数,若步数超过了10步就输出-1;

思路 : 典型的DFS,递归就行,不过注意一下结束条件就行了

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = ;
int ch[maxn][maxn] ;
int ans,m,n;
int dix[] = {,,-,} ;//x轴方向上的变化,分别为上下左右
int diy[] = {,-,,} ;
void dfs(int i,int j,int step)//i,j为初始的坐标,step为走的步数
{
if(step >= ||step>=ans)//如果步数超出10或者步数大于最小移动次数
return ;
int x,y;
for(int h = ; h < ; h++)//四个方向进行遍历
{
x = i+dix[h] ;
y = j+diy[h] ;
if(ch[x][y] == )//如果是阻塞,就跳出
continue ;
while()
{
if(x>=&&x<n&&y >= &&y < m)//没有超出边界
{
if(ch[x][y] == )
{
ch[x][y] = ;//因为撞到阻塞就可以让阻塞消除,并且可以停止
dfs(x-dix[h],y-diy[h],step+);//然后再4个方向进行遍历
ch[x][y] = ;//若是没找到就再恢复原样
break ;
}
if(ch[x][y] == )
{
ans = min(ans,step+);
break;
}
}
else if(!(x>=&&x<n&&y >= &&y < m))
break;
x += dix[h];//如果未遇到阻塞就一直往前走
y += diy[h];
}
}
}
int main()
{
while(cin>>m>>n)
{
if(n == &&m == )
break ;
int x,y ;
ans = ;//ans为从开始位置到目标位置的最少移动次数,初始化为11
for(int i = ; i < n ; i++)
{
for(int j = ; j < m ; j++)
{
cin>>ch[i][j] ;
if(ch[i][j] == )//记录下初始位置的横纵坐标
{
x = i ;
y = j ;
}
}
}
dfs(x,y,) ;
if(ans==) printf("-1\n");
else printf("%d\n",ans);
}
return ;
}

最新文章

  1. ASP.NET Core 中文文档 第三章 原理(16).NET开放Web接口(OWIN)
  2. XMind共享未保存的思维导图的教程
  3. android 判断当前界面是否是桌面
  4. VPS/服务器优化网络、加速方法总结与参考
  5. 安装Linux系统Fedora 23
  6. 《DSP using MATLAB》示例Example4.10
  7. Linux驱动设计——内存与IO访问
  8. RMQ(st)
  9. Codeforces Round #368 (Div. 2) A. Brain&#39;s Photos (水题)
  10. stl map高效遍历删除的方法 [转]
  11. [原]《打造未来的Java》视频笔记
  12. IPC进程间通信 - AIDL+Binder
  13. C/C++变量命名规则
  14. 文本输入框和下拉菜单特效-用正则表达式验证E-mail格式
  15. google Kickstart Round G 2017 三道题题解
  16. timescaledb 集成 madlib
  17. 微信小程序——&lt;radio&gt;&lt;/radio&gt;大小改变
  18. jsoncpp解析拼装数组
  19. spring boot 2.0 源码分析(四)
  20. [多校2015.02.1004 dp] hdu 5303 Delicious Apples

热门文章

  1. 驾照理论模拟考试系统Android源码下载
  2. asp.net图片上传实例
  3. 跟着PHP100第一季学写一个CMS(11-20)
  4. Delphi XE5教程4:程序和单元概述
  5. SQL JOB
  6. JMS消息头
  7. Struts 2简单配置分析
  8. 【ajax跨域】原因原理解决
  9. iTween基础之Move(移动)
  10. Qt入门之信号与槽机制