走迷宫(三):在XX限制条件下,是否走得出。
2024-10-09 02:49:18
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目前提条件:让你输入一个数组,包含一个起点S,一个终点D,一个时间T。(其中X代表墙,.代表此地可行。)
题目要求:在规定的第T秒,问你是否能够走出迷宫。(每走一步耗时1s)。
解题方法:DFS+vis[][]+flag+(新技巧)奇偶剪枝。
#include<iostream>
#include<string.h>
#include<cmath>;
using namespace std; char map[][];
int vis[][]; //(新增)访问标记的数组
int N,M,T;
int sx,dx,sy,dy;
int flag; //(新增)判断状态
int k; //(新增)记录障碍物的个数 int abs(int a,int b)
{
if(a<b)
{
return b-a;
}
else
{
return a-b;
}
} void dfs(int x,int y,int dep) //void()函数内使用“return;”表示跳出此函数。
{
if(dep>T)
{
return ;
}
if(x<||x>=N||y<||y>=M)
{
return ;
} if(flag)
{
return;
}
if(map[x][y]=='D'&&dep==T)
{
flag=;
return ;
} int temp=abs(x-dx)+abs(y-dy); //(新增)奇偶剪枝
temp=T-temp-dep;
if(temp&) //if(走不下去了)
{
return;
} //枚举下一种情况,DFS(...,dep+1);
if(!vis[x-][y]&&map[x-][y]!='X') //(新增)if(下一个点满足的情况)
{
vis[x-][y]=;
dfs(x-,y,dep+);
vis[x-][y]=;
}
if(!vis[x+][y]&&map[x+][y]!='X') //(新增)if(下一个点满足的情况)
{
vis[x+][y]=;
dfs(x+,y,dep+);
vis[x+][y]=;
}
if(!vis[x][y-]&&map[x][y-]!='X') //(新增)if(下一个点满足的情况)
{
vis[x][y-]=;
dfs(x,y-,dep+);
vis[x][y-]=;
}
if(!vis[x][y+]&&map[x][y+]!='X') //(新增)if(下一个点满足的情况)
{
vis[x][y+]=;
dfs(x,y+,dep+);
vis[x][y+]=;
} } int main()
{
while(cin>>N>>M>>T)
{
if(N==&&M==&&T==)
{
break;
} k=;
memset(vis,,sizeof(vis)); //(新增)访问标记数组的初始化。 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;
vis[i][j]=; //(新增)给起点作“已访”标记
}
if(map[i][j]=='D')
{
dx=i;
dy=j;
} if(map[i][j]=='X')
{
k++; //(新增)记录障碍物的个数
}
}
} flag=; //(新增)初始状态为false; if(N*M-k->=T) //(新增)T+k+1(起点S的位置)必须 <= N*M(总的格子数)
{
dfs(sx,sy,);
} if(flag)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
} }
}
最新文章
- web 打开子窗口提交数据或其他操作后 关闭子窗口且刷新父窗口实现
- 通过innobackupex实现对MySQL的完整备份与还原
- RelativeLayout用到的一些重要的属性:
- oracle 时间函数
- JQuery里的原型prototype分析
- 利用Qt调用计算器
- Unity Fresnel Hero(Dota2) Shader
- hbase学习笔记-----REST客户端
- 设置dialog显示,自定义时间到后dialog消失
- Android基础之CountDownTimer 倒计时类
- 更改DataTable列名方法
- truncate 和 delete 差异
- Android开发之漫漫长途 Ⅳ——Activity的显示之ViewRootImpl初探
- TCP/IP,Web世界的基本规则
- hdu 1394 逆序对(nlgn+o(n) )
- 9、Qt Project之简单的数据库接口
- day07 深浅拷贝
- redis排序
- 记一次线上bug排查-quartz线程调度相关
- Java SE学习【三】——JDBC