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++的代码，没有什么太大的改进，只是改写，就不帖出来了。
腾讯云开发者
