DFS练习-HDU1010
题目来源：HDU1010
DFS的基本原则已经差不多了，但是一些技巧仍然比较难想，所以还是加强练习，然后总结一下。
还是先看题意 ，指定迷宫的长，宽以及走出迷宫的具体时间N,M,T。
其中(1 < N, M < 7; 0 < T < 50)。
在这个迷宫中，从起点 ‘S’ 出发，每经过一个格子就花费一秒，不可掉头。
而要做的就是判断是否有一条从起点到终点 ‘D’ 的路恰好花费T秒。
如果有就输出YES，否则就是NO了。
再看代码：
#include<stdio.h>
#include<math.h>
char maze[10][10]; //迷宫
int flag; //YES OR NO
int N, M, T; //迷宫的长和宽，和限定的时间
int dirction[4][2] =
{
{ 0,1 },{ 1,0 },
{ 0,-1 },{ -1,0 }
}; //四个遍历方向
int sx, sy; //起点坐标
int gx, gy; //终点坐标
void dfs(int x, int y, int time)
{
if (flag)
return; //条件符合
if (x == gx&&y == gy&&time == T)
{
flag = 1;
return;
}
if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
return;
if (time > T)
return;
for (int i = 0; i < 4; i++)
{
int dx = x + dirction[i][0];
int dy = y + dirction[i][1];
if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
{
maze[dx][dy] = 'X';
dfs(dx, dy, time + 1);
maze[dx][dy] = '.';
}
}
}
int main(void)
{
while (scanf("%d %d %d", &N, &M, &T) != EOF)
{
if ((N + M + T) == 0)
break;
int i, j;
for (i = 0; i < N; i++)
{
getchar();
for (j = 0; j < M; j++)
{
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S')
{
sx = i;
sy = j;
}
if (maze[i][j] == 'D')
{
gx = i;
gy = j;
}
}
}
getchar();
maze[sx][sy] = 'X';
flag = 0;
dfs(sx, sy, 0);
if (flag == 1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}1.main函数
int main(void)
{
while (scanf("%d %d %d", &N, &M, &T) != EOF)
{
if ((N + M + T) == 0)
break;
int i, j;
for (i = 0; i < N; i++)
{
getchar();
for (j = 0; j < M; j++)
{
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S')
{
sx = i;
sy = j;
}
if (maze[i][j] == 'D')
{
gx = i;
gy = j;
}
}
}
getchar();
maze[sx][sy] = 'X';
flag = 0;
dfs(sx, sy, 0);
if (flag == 1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}按照题意，输入三个数，迷宫的长宽，以及规定时间，N,M,T。
第一个if控制主循环退出，即0 0 0退出 。
接着用循环记录迷宫，顺便记录下起点和终点的坐标值。
设置判断成功与否的标志的flag为0，就开始DFS了。
2.dfs函数
void dfs(int x, int y, int time)
{
if (flag)
return; //条件符合
if (x == gx&&y == gy&&time == T)
{
flag = 1;
return;
}
if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
return; //剪枝2
if (time > T)
return; //剪枝1
for (int i = 0; i < 4; i++)
{
int dx = x + dirction[i][0];
int dy = y + dirction[i][1];
if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
{
maze[dx][dy] = 'X';
dfs(dx, dy, time + 1);
maze[dx][dy] = '.';
}
}
}第一个if判断是否找到符合题意的解，有就退出，不再搜索。
第二个如果在规定的时间内到达了终点的话，就设置flag=1,即存在这样的解
if (flag)
return; //条件符合
if (x == gx&&y == gy&&time == T)
{
flag = 1;
return;
}循环主体部分：
for (int i = 0; i < 4; i++)
{
int dx = x + dirction[i][0];
int dy = y + dirction[i][1];
if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
{
maze[dx][dy] = 'X';
dfs(dx, dy, time + 1);
maze[dx][dy] = '.';
}
}四个方向的遍历，如果这个点的坐标满足要求，即在迷宫之内并且迷宫中这个点不是墙。
DFS中已经搜索过的点不能重复搜索，所以需要先将这个点设置为墙，然后dfs，再复原，进行回溯的操作。
maze[dx][dy] = 'X';
dfs(dx, dy, time + 1);
maze[dx][dy] = '.';剪枝问题
注释上的剪枝1：
if (time > T)
return; //剪枝1当消耗的时间超过了题目规定的时间，说明已经不存在符合题意的解，那应该不需要再往下搜索了。
如果不包含剪枝2，直接提交也没办法通过，因为会超时 QAQ。
注释上的剪枝2：
if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
return; //剪枝2这个剪枝包含了01剪枝，也叫做奇偶剪枝。
2.1奇偶剪枝
这就是技巧，弄清除原理，就好理解了QWQ。
先给出一个6X6的数组：
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
好像没什么意义……好吧，主要是看步数。
从0开始走，走1步会走到1；从1开始走，走1步会走到0.
从0开始走，走2步会走到0；从1开始走，走2步会走到1.
从0开始走，走3步会走到1；从1开始走，走3步会走到0.
从0开始走，走4步会走到0；从1开始走，走4步会走到1.
从0开始走，走5步会走到1；从1开始走，走5步会走到0.
从0开始走，走6步会走到0；从1开始走，走6步会走到1.
……
找找规律，0走偶数步到0，1同理；0走奇数步到1，1走奇数步到0
但是这个和这道题有什么关系？
所以先做一个假设，题目给出如上数组，这个数组上都是可以通过的，即都是 ‘.’
起点是（1，1），终点是（5，5）。
这个时候走9步就可以到达终点了。
那么T如果给的是13，能否在时间内恰好到达？
不能。
换一组数据，起点是（0，4），终点是（4，3），T=6，能否成功？
看下上面的数组，（0，4）是0，（4，3）是1，T是偶数，所以不能到达。
但是看数组并不好，一般这样来判断是0还是1：
（0，4）是（0+4）%2=0
（4，3）是（4+3）%2=1
那么将（0，4）和（4，3）这一组数据中的T换成7，7是奇数，是否能说明一定成功？
很明显不能，如果这样就能判断的话，还要dfs干嘛？！ (O_O)
在刚才的假设中，实际只需要5步就可以到达终点，所以T=7仍然不符合题意。
所以，还需要一个判断，实际距离和剩余时间的比较。
距离：abs(sx-gx)+abs(sy-gy)，在只能直走的情况下，这就是最短的距离了。
所以abs(sx-gx)+abs(sy-gy) < Time ,就能到达了吗？
不一定。因为这样的话，才有可能到达。
如果abs(sx-gx)+abs(sy-gy) > Time 会发生什么？
说明在没有墙的情况下，那只小狗沿着最短的路都不可能到达终点，那么一定是无解的了。
最后综合一下的条件：
abs(sx-gx)+abs(sy-gy) > Time （Time是剩余时间）
奇偶性：
(x+y)%2与(gx+gy)%2与Time%2 (gx,gy是终点坐标，x,y是当前点的坐标，Time是剩余时间)
可以和起来判断：
(x + gx + y + gy + Time ) % 2 != 0
以上条件都不可能到达。
这就是剪枝2的内容。
那么结果是怎么样的呢？
第一行就是一开始的代码结果，虽然过了，但是时间上感觉不是太好。
所以有了第二行以及第三行。
剪枝3
这个我没有想到，通过别人的代码得知。
通过迷宫可以得知墙体的数目，这就可以算出‘.’的数目了，即N*M-sum.
sum是墙体的数目.
这代表这只小狗在迷宫内最多只能待这么长的时间。
如果这个时间比规定的时间T还要小，小狗根本不能存活了。
所以，N*M-sum>T
最后的代码
#include<stdio.h>
#include<math.h>
char maze[10][10]; //迷宫
int flag; //YES OR NO
int N, M, T; //迷宫的长和宽，和限定的时间
int dirction[4][2] =
{
{ 0,1 },{ 1,0 },
{ 0,-1 },{ -1,0 }
}; //四个遍历方向
int sx, sy; //起点坐标
int gx, gy; //终点坐标
void dfs(int x, int y, int time)
{
if (flag)
return; //条件符合
if (x == gx&&y == gy&&time == T)
{
flag = 1;
return;
}
if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
return;
if (time > T)
return;
for (int i = 0; i < 4; i++)
{
int dx = x + dirction[i][0];
int dy = y + dirction[i][1];
if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
{
maze[dx][dy] = 'X';
dfs(dx, dy, time + 1);
maze[dx][dy] = '.';
}
}
}
int main(void)
{
while (scanf("%d %d %d", &N, &M, &T) != EOF)
{
if ((N+M+T)==0)
break;
int i, j, sum=0;
for (i = 0; i < N; i++)
{
getchar();
for (j = 0; j < M; j++)
{
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S')
{
sx = i;
sy = j;
}
if (maze[i][j] == 'D')
{
gx = i;
gy = j;
}
if (maze[i][j] == 'X')
sum++;
}
}
getchar();
if (N*M - sum <= T)
{
printf("NO\n");
continue;
}
maze[sx][sy]='X';
flag = 0;
dfs(sx, sy, 0);
if (flag==1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
至于第三个C++的代码，没有什么太大的改进，只是改写，就不帖出来了。
最新文章
- Webpack、Browserify和Gulp
- iPhone开发常问的十个问题
- 【linux】暂时解决sis m672(神舟F4000 D9) linux驱动 宽屏分辨率的问题?
- 实例化新的一个(new)
- 15款免费WiFi入侵破解安全测试工具
- js调用函数时传入的参数个数与函数定义时的参数个数不符时的操作
- 转载：MyEclipse安装插件的几种方法
- Mac主机映射到域名
- DEDECMS开启邮箱验证通知的解决方法
- PySpider 爬虫系统
- python入门（一）：进入python的交互模式、pip的使用和数据类型
- web标准 浏览器介绍 开发工具介绍 HTML介绍 HTML颜色介绍 规范 HTML结构详解 {前端之前端初识}
- golang中tcp socket粘包问题和处理
- Notes of Daily Scrum Meeting（12.21）
- bat 十进制转16进制
- Mac 下安装Ruby环境
- SAP CX Upscale Commerce : SAP全新推出的电商云平台
- LeNet
- Walle代码发布
- jquery与javescript的区别（一）