[VijosP1656]萌萌赶考 题解

题目大意：

　　有一个地图，有障碍，不能重复经过一点（但起点可以），判断能否恰好在t时刻从起点到达终点。

思路:

　　一开始DFS一遍，30分，于是要有优化减枝。最重要的是从起点到终点的距离的奇偶性是与起点与终点的曼哈顿距离的奇偶性一样（因为远离“最短路”后必将回来，所以会加一个偶数，奇偶性不变）当然还有其他，如最短距离+当前时间>要求时间则减去、搜索方向为先左上再右下。

代码：

#include<cstdio>
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int n,m,t,i,j,b,e,a[9][9];
char s[9];

int abs(int x) { return x>0?x:-x; }

bool dfs(int x,int y,int k)
{
    if (k==t)
    {
        if (x==b && y==e) return 1;
        return 0;
    }
    if (abs(x-b)+abs(y-e)+k>t) return 0;
    for (int i=0,p,q;i<4;++i)
        if (a[p=x+dx[i]][q=y+dy[i]])
        {
            a[p][q]=0;
            if (dfs(p,q,k+1)) return 1;
            a[p][q]=1;
        }
    return 0;
}

int main()
{
    for (scanf("%d%d%d",&n,&m,&t);n && m && t;scanf("%d%d%d",&n,&m,&t))
    {
        for (i=1;i<n+2;++i)
            for (j=1;j<m+2;++j) a[i][j]=0;
        for (i=1;i<=n;++i)
        {
            scanf("%s",s+1);
            for (j=1;j<=m;++j)
                if (s[j]!='H')
                {
                    if (s[j]=='D') b=i,e=j;
                    a[i][j]=1;
                }
        }
        if ((((b+e)&1)==(t&1)) && dfs(1,1,0)) printf("Yes
");
        else printf("No
");
    }
    return 0;
}