学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目的意思比较简单。。

走T步从S走到D。。。迷宫最大8X8的。。bfs肯定不行了。。。因为bfs一般求解的是最短的时间或者步数。。dfs果断之。。

表示，不会写dfs的。。。那就学呗。。。。。

如果纯暴力深搜的话，肯定会TLE。。。那就剪枝吧。。

这个题，有比较多是剪枝方式。。

1.步数剪枝。。。如果总共能走的步数还要小于T的话。。一定会是NO。。

2.如果中间走到D了，并且走的步数不等于T。。这条路就可以走到这里了。。

3.走的步数大于T了。。也就不行了。。

4.奇偶剪枝。。。

可能还有其他什么样的剪枝方法。。。还好的是，这个问题的数据还是比较水的。。。所以，就加了一个步数剪枝就水过了。。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define CLR(arr, val) memset(arr, val, sizeof(arr))

const int N = 10;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {-1, 1, 0, 0};
char map[N][N];
int n, m, t, bx, by;
bool flag, vis[N][N];
void dfs(int x, int y, int step)
{
    if(step > t) return ;
    if(flag) return ;
    if(step == t && map[x][y] == 'D'){
        flag = true;
        return ;
    }
    if(map[x][y] == 'D') return ;
    for(int i = 0; i < 4; i ++){
        int gox = x + dx[i], goy = y + dy[i];
        if(gox < 1 || gox > n || goy < 1 || goy > m || vis[gox][goy] || map[gox][goy] == 'X') continue;
        vis[gox][goy] = true;
        dfs(gox, goy, step + 1);
        vis[gox][goy] = false;
    }
    return ;
}

int main()
{
//    freopen("1.txt", "r", stdin);
    while(scanf("%d %d %d", &n, &m, &t) &&  (n || m || t)){
        getchar();
        int maxstep = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                scanf("%c", &map[i][j]);
                if(map[i][j] == 'S'){
                    bx = i; by = j;
                }
                if(map[i][j] == '.') ,maxstep ++;
            }
            getchar();
        }
        if(maxstep + 1 < t){// step 
            puts("NO");
            continue;
        }
        flag = false; CLR(vis, false);
        vis[bx][by] = true;
        dfs(bx, by, 0);
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

所有的知识都是从不会到会的。。

有机会一定要学习那个奇偶剪枝。。。