hdu 1010 的心得体会

此题大意：从S走到D，要求恰好为T步，地图中点为路，X为墙（不能通过）。

搜索就像一堆警察在一片树林里逮一个强奸犯，警察掌握了一些信息但是又不可能知道歹徒的具体位置。

深度优先搜索就是一条路或者说一个方向搜到底（直到前面有悬崖或者歹徒找到了），广度优先搜索就是那种地毯式搜索（100个人站一排向前突进）。

此题采用深度优先搜索的方法，要注意满足哪些条件就不用搜这条路了（吾乃天命之子，可预知悬崖。。。）

奇偶剪枝（名字倒是取得很6，淫才）：如多从一个点到另一个点的最短距离是偶数，那么所有路径都是偶数，所以此时奇数步走完是不可能的。（自己领悟去吧，领悟了记得评论告我咋这么神奇呢.............）

嗯........剩下的细节看代码吧。。溜了

#include<iostream>
using namespace std;
char map[8][8];
int direction[2][4]={0,1,0,-1,
                     1,0,-1,0};
int flag;
int N,M,T,ex,ey; //end  x,y
int point;       //点的个数
int abs(int x)
{
    return x>0?x:-x;
}
void f(int sx,int sy,int num)
{
    int shortdi;//short distance 最短距离
    int x,y;
    int mark;
    if(flag==1)return;
    if(sx==ex&&sy==ey&&num!=T)return;
    if(sx==ex&&sy==ey&&num==T)
    {
        flag=1;
        return;
    }
    shortdi=abs(sx-ex)+abs(sy-ey);
    if((shortdi+T-num)%2||T-num<shortdi)return;
    for(int i=0;i<4;i++)
    {
        if(map[sx][sy]=='.'){mark=1;map[sx][sy]='X';}
        else mark=0;
       
        x=sx;y=sy;
        x+=direction[0][i];
        y+=direction[1][i];
        if(x>=0&&x<N&&y>=0&&y<M&&(map[x][y]=='.'||map[x][y]=='D'))
        {
            f(x,y,num+1);
        }
        if(mark)map[sx][sy]='.';
    }
}
int main()
{
    int sx,sy;       //start x,y
    while(cin>>N>>M>>T)
    {
        if(N==0&&M==0&&T==0)break;
        point=0;
        flag=0;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
                if(map[i][j]=='D')
                {
                    ex=i;
                    ey=j;
                }
                if(map[i][j]=='.')
                point++;
            }
        }
        if(point<T-1)
        {
         cout<<"NO\n";
         continue;
        }
       
        f(sx,sy,0);
        if(flag==1)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

//Number  1