Tempter of the Bone

题意:给定你起点S，和终点D，问你是否能在 T 时刻恰好到达终点D。

Sample Input

4 4 5

S.X.

..X.

..XD

....

3 4 5

S.X.

..X.

...D

0 0 0

Sample Output

NO

YES

奇偶剪枝优化；开始时是朴素的当时间t > T || (t >= T&&g[][] != 'D')时，结束搜索；直接TLE了；之后看了题解说还要加一个奇偶剪枝，就是对每个坐标；将该点坐标的横坐标和纵坐标加起来奇偶性，就是两点横纵坐标之和同奇偶即斜对角关系；很容易知道之后如果S和D的奇偶性不同，还和t的奇偶性对不上就直接output了；但是有个疑问就是问什么一个看似作用不大的"判断"，却使时间减少了几百ms???请大牛指教；还看了statics,前面都是0ms过的，很是神奇

ps:对于里面粗略的看是否能到达，本来想写个BFS的，但是没写)

//Accepted    1010    717MS    1572K    1411 B
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 1;i <= n;i++)
#define MS0(a) memset(a,0,sizeof(a))
typedef pair<int,int> PII;
#define A first
#define B second
int N,M,T;
int f[10][10];
char g[10][10];
bool flag;
bool check(int nx,int ny)
{
    if(g[nx][ny] == 'D') return true;
    if(nx > N||ny > M||g[nx][ny] != '.'||f[nx][ny]) return false;
    return true;
}
int dir[2][4] = {{0,1,0,-1},{1,0,-1,0}};
void dfs(int sx,int sy,int t)
{
    if(g[sx][sy] == 'D' && t == T){
        flag = true ;
        return ;
    }
    if(t >= T||g[sx][sy] == 'D') return ;
    f[sx][sy] = 1;
    for(int i = 0;i < 4;i++){
        int nx = sx + dir[0][i] , ny = sy + dir[1][i];
        if(check(nx,ny)&&!flag){
            dfs(nx,ny,t+1);
            f[nx][ny] = 0;
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&N,&M,&T) == 3, N != 0){
        MS0(f);
        int sy,sx,ex,ey,i,j,t = 0;
        for(i = 1; i<= N;i++){
            scanf("%s",g[i]+1);
            for(j = 1;j <= M;j++)
                if(g[i][j] == 'D')
                    ex = i,ey = j;
                else if(g[i][j] == 'S')
                    sx = i,sy = j;
        }
        if(abs(sx+sy-ex-ey)%2 == t%2||abs(sx+sy-ex-ey)>T){
            puts("NO");
            continue;
        }
        flag = 0;
        dfs(sx,sy,t);
        puts(flag?"YES":"NO");
    }
}

View Code

hdu1010 Tempter of the Bone

Tempter of the Bone

推荐阅读