有两点需要注意,第一点就是,题意是指在第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')))
            {
                    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;
    }
}
 
 
 
 
 
 
 

最新文章

  1. uva 820(最大流)
  2. ashx 文件 与js文件数据交互
  3. swun 1184
  4. 大晚上装CocoaPods出现错误坑爹
  5. windows 消息机制的学习
  6. 打破了中国电信华为无线路由猫(HG522-C)自己主动拨号+任意数量的计算机+iTV
  7. Microsoft.VisualBasic.dll的妙用and 改善C#公共程序类库质量的10种方法
  8. linux模拟实现主机跨路由通信
  9. 用js 获取url 参数 页面跳转 ? 后的参数
  10. jQuery初识之选择器、样式操作和筛选器(模态框和菜单示例)
  11. .Net代码控制PrivateBinPath和ConfigurationFile的位置
  12. 日志模块logging
  13. DevExpress XtraScheduler日程管理控件应用实例(2)-- 深入理解数据存储
  14. 数据库之MySQL的介绍与使用20180703
  15. Jupyter 安装并配置工作路径[转]
  16. JS中的唯一容器:数组
  17. redis和memcache缓存击穿,缓存失效问题
  18. 【luogu P3384 树链剖分】 模板
  19. 1237: [SCOI2008]配对
  20. bzoj2973石头游戏——矩阵乘法

热门文章

  1. defineProperty和Proxy
  2. sap软件功能介绍及主要功能(模块)有哪些?
  3. 关于SQLsever2012报错的一些经验总结
  4. make vscode portable together with its extensions
  5. Py_excel
  6. Outlook怎么合并相同邮件?设置Outlook邮件为对话模式
  7. unity GetComponent在android端获取对象错误
  8. IEC104
  9. UltiSnips安装及设置
  10. angularjs 1.4.x 内部组件介绍