2018-07-14-奇偶剪枝

题目：Problem - 1010

刚开始超时，网上查了一下，了解到了奇偶剪枝。改了一下，WA了一天，最后，看到：

HDOJ 1010 HDU 1010 Tempter of the Bone ACM 1010 IN HDU - MiYu - 博客园

感谢提醒。原来用的是gets,scanf("%s"),getchar,scanf("%c"),都没有通过,

最后用scanf(" %c ")和cin通过了。

不过，我还有一点想不明白的是，效率应该如何计算呢？超时的时候记录了一下递归的次数，高得惊人，而我却无法从理论上推导出来这个值。

源代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

#define YES 1
#define NO 0

int n,m,t;
char *p=NULL;
//long long cnt=0;
int A[]={-1,1,0,0},B[]={0,0,-1,1};

int search(int n1,int n2,int depth)
{
//    cnt++;
    if( n1<0 || n1>=n || n2<0 || n2>=m)
    {
        return NO;
    }
    if(p[n1*m+n2]=='X')
    {
        return NO;
    }
    if(p[n1*m+n2]=='D')
    {
        if(depth==t)
        {
            return YES;
        }
        else
        {
            return NO;
        }
    }
    if(depth>t)
    {
        return NO;
    }
    depth++;
    p[n1*m+n2]='X';
    int i;
    for(i=0; i<4 && search(n1+A[i],n2+B[i],depth)!=YES ;i++);
    p[n1*m+n2]='.';
    if(i>=4)
        return NO;
    else
        return YES;
}

int main()
{
    while(1)
    {
        int i,j,si,sj,ei,ej;
        scanf("%d%d%d",&n,&m,&t);
        if(n==0 && m==0 && t==0)
            break;
        p=(char*)calloc(n*m,sizeof(char));
        assert(p);
        getchar();
        for(i=0;i<n;i++)
        {
//            gets(p+i*m);
//            scanf("%s",p+i*m);
            for(j=0;j<m;j++)
            {
//                p[i*m+j]=getchar();
//                scanf("%c",&p[i*m+j]);
//                putchar(p[i*m+j]);
//                cin >> p[i*m+j] ;
                scanf(" %c ",p+i*m+j);
                switch(p[i*m+j])
                {
                    case 'S':
                        si=i;
                        sj=j;
                        break;
                    case 'D':
                        ei=i;
                        ej=j;
                        break;
                }
            }
        }
        i=si-ei+sj-ej;
        i=i<0?-i:i;
        if( t<i || (i&0x1)!=(t&0x1) )
        {
            printf("NO\n");
        }
        else
        {
//            cnt=0;
            if(search(si,sj,0)==YES)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
//            printf("cnt=%lld\n",cnt);
        }
        free(p);
    }
    return 0;
}