HDOJ--1010题C++
2024-10-21 23:18:23
有两点需要注意,第一点就是,题意是指在第T秒时门才打开,并不是越早到门口就能越早出去,而是只要存在指定长的路径即可以出去。
第二点,每次深搜发现答案不符都必须将点重新初始化。
#include<iostream>
#include<utility>
#define INF 10000
using namespace std;
char maze[100][7];
int d[100][7];
int n,m,t,start_i,start_j,end_i,end_j;
int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
bool dfs(int i,int j);
int main()
{
while(cin>>n>>m>>t && n &&m
&& t)
{
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>maze[i][j];
if(maze[i][j]=='S')
{
start_i=i;
start_j=j;
}
if(maze[i][j]=='D')
{
end_i=i;
end_j=j;
}
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
d[i][j]=INF;
d[start_i][start_j]=0;
if(dfs(start_i,start_j))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
bool dfs(int i,int j)
{
if(i==end_i && j==end_j)
{
if(d[i][j]==t)
{
d[i][j]=INF;
return true;
}
else
{
d[i][j]=INF;
return false;
}
}
else
{
for(int k=0; k<4; k++)
{
int nx=dx[k]+i,ny=dy[k]+j;
if( nx>=0 &&nx < n &&ny>=0 && ny<m && (d[nx][ny]==INF) &&((maze[nx][ny]=='.')||(maze[nx][ny]=='D')))
{
#include<iostream>
#include<utility>
#define INF 10000
using namespace std;
char maze[100][7];
int d[100][7];
int n,m,t,start_i,start_j,end_i,end_j;
int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0};
bool dfs(int i,int j);
int main()
{
while(cin>>n>>m>>t && n &&m
&& t)
{
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>maze[i][j];
if(maze[i][j]=='S')
{
start_i=i;
start_j=j;
}
if(maze[i][j]=='D')
{
end_i=i;
end_j=j;
}
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
d[i][j]=INF;
d[start_i][start_j]=0;
if(dfs(start_i,start_j))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
bool dfs(int i,int j)
{
if(i==end_i && j==end_j)
{
if(d[i][j]==t)
{
d[i][j]=INF;
return true;
}
else
{
d[i][j]=INF;
return false;
}
}
else
{
for(int k=0; k<4; k++)
{
int nx=dx[k]+i,ny=dy[k]+j;
if( nx>=0 &&nx < n &&ny>=0 && ny<m && (d[nx][ny]==INF) &&((maze[nx][ny]=='.')||(maze[nx][ny]=='D')))
{
d[nx][ny]=d[i][j]+1;
if(dfs(nx,ny))
{
d[nx][ny]=INF;
return true;
}
else
d[nx][ny]=INF;
}
}
d[i][j]=INF;
return false;
}
}
if(dfs(nx,ny))
{
d[nx][ny]=INF;
return true;
}
else
d[nx][ny]=INF;
}
}
d[i][j]=INF;
return false;
}
}
最新文章
- uva 820(最大流)
- ashx 文件 与js文件数据交互
- swun 1184
- 大晚上装CocoaPods出现错误坑爹
- windows 消息机制的学习
- 打破了中国电信华为无线路由猫(HG522-C)自己主动拨号+任意数量的计算机+iTV
- Microsoft.VisualBasic.dll的妙用and 改善C#公共程序类库质量的10种方法
- linux模拟实现主机跨路由通信
- 用js 获取url 参数 页面跳转 ? 后的参数
- jQuery初识之选择器、样式操作和筛选器(模态框和菜单示例)
- .Net代码控制PrivateBinPath和ConfigurationFile的位置
- 日志模块logging
- DevExpress XtraScheduler日程管理控件应用实例(2)-- 深入理解数据存储
- 数据库之MySQL的介绍与使用20180703
- Jupyter 安装并配置工作路径[转]
- JS中的唯一容器:数组
- redis和memcache缓存击穿,缓存失效问题
- 【luogu P3384 树链剖分】 模板
- 1237: [SCOI2008]配对
- bzoj2973石头游戏——矩阵乘法