链接 :
思路 : 如果直接爆搜的话, 会搜到天荒地老.... QAQ ...., 所以就得利用一些技巧, 因为题目说的是小狗能否在 $T (s)$ 能够恰好到达 $Door$ , 所以可以利用 奇偶剪枝 来剪掉多余搜索
奇偶剪枝 : 假设只能上下左右移动, 现在起点为 $(sx, sy)$ , 终点为 $(ex, ey)$ , 要求恰好 $T$ 步从 $(sx, sy)$ 到达 $(ex, ey)$, 因此可以得到一个结论, 若 $T - [abs(sx - ex) + abs(sy - ey)] 为奇数, 则无法在T步恰好到达, 反之则可以$, 再补充一点 $ [abs(sx - ex) + abs(sy - ey)] $ 称为曼哈顿路径
/************************************************************************* > File Name: E.cpp > Author: > Mail: > Created Time: 2017年11月26日 星期日 10时51分05秒 ************************************************************************/#include#include #include #include using namespace std;#define MAX_N 10int N, M, T;int vis[MAX_N][MAX_N];char G[MAX_N][MAX_N];int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};bool flag = 0;struct Point { Point() : x(0), y(0){} Point(int x, int y) : x(x), y(y){} int x, y;};Point st, ed;int manhattan_dist(Point sre, Point des) { return fabs(sre.x - des.x) + fabs(sre.y - des.y);}int check(Point pt) { if (pt.x < 0 || pt.x >= N || pt.y < 0 || pt.y >= M) return 0; if (vis[pt.x][pt.y]) return 0; if (G[pt.x][pt.y] == 'X') return 0; return 1;}// 直接曼哈顿路径 + 奇偶剪枝void DFS(Point pt, int now_time) { if (pt.x == ed.x && pt.y == ed.y && now_time == T) { flag = 1; return; } if (flag) return; // 曼哈顿路径 + 奇偶剪枝 int tstep = T - now_time - manhattan_dist(pt, ed); if (tstep < 0 || (tstep & 1)) return; vis[pt.x][pt.y] = 1; for (int i = 0 ; i < 4 ; ++i) { Point temp(pt.x + dx[i], pt.y + dy[i]); if (!check(temp)) continue; vis[temp.x][temp.y] = 1; DFS(temp, now_time + 1); vis[temp.x][temp.y] = 0; }}void solve() { memset(vis, 0, sizeof(vis)); for (int i = 0 ; i < N ; ++i) { for (int j = 0 ; j < M ; ++j) { if (G[i][j] == 'S') st.x = i, st.y = j; if (G[i][j] == 'D') ed.x = i, ed.y = j; } } vis[st.x][st.y] = 1; DFS(st, 0); if (flag) { printf("YES\n"); } else { printf("NO\n"); }}int main() { // freopen("./in.in", "r", stdin); while (scanf("%d%d%d", &N, &M, &T) != EOF) { flag = 0; if (N == 0 && M == 0 && T == 0) break; memset(G, 0, sizeof(G)); for (int i = 0 ; i < N ; ++i) { getchar(); scanf("%s", G[i]); } solve(); } return 0;}