题目链接。
分析:
首先,感慨一下。。我竟然做出来了一个难度为2的(第一次)。。感谢CCTV。
这题呢。。直接DFS就可以了。不过不剪枝的话TLE。
第一种剪枝是如果所有可走的点的总和也小于T直接输出NO。
这一种剪枝可以从TLE到843ms
第二种是从课件上学的奇偶性剪枝
可以从TLE到 453ms
最后把两种方法合并。竟然达到了62ms
(掌声响起。。)
奇偶性剪枝。如下图所说。
62ms AC代码如下;
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define MAXN 10 char G[MAXN][MAXN]; int n, m, T, vis[MAXN][MAXN]; int ex, ey; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int dfs(int x, int y, int cur){ int d, tmp; tmp = T-cur-abs(ex-x)-abs(ey-y); if(tmp<0 || tmp % 2 == 1) return 0; for(d=0; d<4; d++){ int nx = x+dx[d], ny = y+dy[d]; if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny]){ if(G[nx][ny]=='.'){ vis[nx][ny] = 1; if(dfs(nx, ny, cur+1)) return 1; vis[nx][ny] = 0; } else if(G[nx][ny] == 'D' && cur == T-1) return 1; } } return 0; } int main(){ int i, j, space; while(scanf("%d %d %d", &n, &m, &T) == 3){ if(n == 0 && m == 0 && T == 0) break; for(i=0; i<n; i++){ scanf("%s", G[i]); } space = 0; for(i=0; i<n ;i++){ for(j=0; j<m; j++){ if(G[i][j] == '.') space++; if(G[i][j] == 'D'){ ex = i; ey = j; } } } if(T>space+1) {printf("NO\n"); continue;} for(i=0; i<n; i++){ for(j=0; j<m; j++){ if(G[i][j] == 'S') break; } if(j<m) break; } memset(vis, 0, sizeof(vis)); vis[i][j] = 1; if(dfs(i, j, 0)) printf("YES\n"); else printf("NO\n"); } return 0; }