需要剪枝否则会超时,然后就是基本的深搜了

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 1005 using namespace std; char Map[MAX][MAX]; int time,n,m,sx,sy,ex,ey,v[][]={{,},{,},{-,},{,-}},ok; bool check(int x,int y)
{
if(x>= && x<n && y>= && y<m && Map[x][y]!='X')
return true;
return false;
} void DFS(int x,int y,int step)
{
if(x==ex && y==ey && step==time)
{
ok=;
return;
}
else if(step >= time || ok)
return;
for(int i=;i<;i++)
{
int new_x=x+v[i][];
int new_y=y+v[i][];
if(check(new_x,new_y))
{
Map[new_x][new_y]='X';
DFS(new_x,new_y,step+);
Map[new_x][new_y]='.';
}
}
} int main()
{
while(scanf("%d%d%d",&n,&m,&time),n+m+time)
{
ok=;
for(int i=;i<n;i++)
scanf("%s",Map[i]);
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(Map[i][j]=='S')
{
sx=i;
sy=j;
}
if(Map[i][j]=='D')
{
ex=i;
ey=j;
}
}
}
int k1=abs(sx-ex);
int k2=abs(sy-ey);
if((time-(k1+k2))%)//奇偶剪纸
{
printf("NO\n");
continue;
}
if(sx==ex && sy==ey)
{
printf("YES\n");
continue;
}
Map[sx][sy]='X';
DFS(sx,sy,);
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return ;
}

最新文章

  1. css选择器([class*=&quot; icon-&quot;], [class^=icon-] 的区别)
  2. 让ASP.NET Web API支持text/plain内容协商
  3. rsync拉取远程文件
  4. ZooKeeper实践方案:(7) 分布式锁
  5. 基于UDP协议的网络编程
  6. Vim插件管理 -- Vundle
  7. 单源最短路径(1):Dijkstra 算法
  8. Spring Security 入门(1-3-3)Spring Security - logout 退出登录
  9. java操作FTP的一些工具方法
  10. vue 热加载问题
  11. windos下完全卸载MySQL
  12. python对象的不同参数集合
  13. 快速构建一个使用axios的vue应用程序(转)
  14. 20165312 2017-2018-2《JAVA程序设计》第8周学习总结
  15. 读取HTML文件进行格式化解析
  16. Linux shell 菜鸟学习笔记....
  17. for XX in XX结构
  18. HDU 2159 FATE (dp)
  19. day7 opencv+python 读取视频,没有东西
  20. Oracle创建表管理表

热门文章

  1. CentOS安装Ruby组件
  2. C# 语言规范_版本5.0 (第5章 变量)
  3. python读取CSV文件
  4. LightOJ 1337 F - The Crystal Maze (bfs)
  5. 大数据除法(Large data division)
  6. Openjudge-计算概论(A)-骑车与走路
  7. 【入门一】一些简单的C程序及VS的安装
  8. Python从json中提取数据
  9. 依赖跟踪如何工作的(How dependency tracking works)
  10. 使用gulp构建nodejs,你只需要记住5个函数