hdu - 1010 Tempter of the Bone (dfs+奇偶性剪枝) && hdu-1015 Safecracker(简单搜索)

http://acm.hdu.edu.cn/showproblem.php?pid=1010

这题就是问能不能在t时刻走到门口,不能用bfs的原因大概是可能不一定是最短路路径吧。

但是这题要过除了细心外，还需要强力的剪枝。

奇偶性剪枝：参考 http://www.cppblog.com/Geek/archive/2010/04/26/113615.html

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 char map[][];

 int n,m,t,di,dj;

 bool escape;

 int dir[][]={{,-},{,},{,},{-,}};

 void dfs(int si,int sj,int cnt)

 {

     if(cnt>) return;

     if(escape) return;

    if(si>n||sj>m||si<=||sj<=) return;

    if(cnt==t&&si==di&&sj==dj)    escape=;

    if(escape) return;

    if(cnt>=t) return;

    int i,temp;

    temp=(t-cnt)-abs(si-di)-abs(sj-dj);

    if(temp<||temp&) return;

    for(i=;i<;i++){

       if(map[si+dir[i][]][sj+dir[i][]]!='X')

       {

          map[si+dir[i][]][sj+dir[i][]]='X';

          dfs(si+dir[i][],sj+dir[i][],cnt+);

          map[si+dir[i][]][sj+dir[i][]]='.';

       }

    }

    return;

 }

 int main()

 {

     int i,j,si,sj;

     while(cin>>n>>m>>t)

     {

       if(n==&&m==&&t==) break;

       int wall=;

       for(i=;i<=n;i++)

          for(j=;j<=m;j++)

          {

             cin>>map[i][j];

             if(map[i][j]=='S') { si=i; sj=j; }

             else if(map[i][j]=='D') { di=i; dj=j; }

             else if(map[i][j]=='X') wall++;

          }

        if(n*m-wall<=t)

        {

            cout<<"NO"<<endl;

            continue;

        }

        escape=;

        map[si][sj]='X';

        dfs(si,sj,);

        if(escape) cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return ;

 }

http://acm.hdu.edu.cn/showproblem.php?pid=1015

给定一个字符串和一个数n,然后再字符串中找出5个字符，满足题目中的等式并且字典序最大。

输入之后先把字符串从大到小排序，然后搜索即可。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 bool cmp(char a,char b)

 {

     return a>b;

 }

 int k,j,flag,vis[];

 char s[],ss[],res[];

 bool judge(int v,int w,int x,int y,int z)

 {

     if(v-w*w+x*x*x-y*y*y*y+z*z*z*z*z==k)

         return ;

     return ;

 }

 void dfs(int x)

 {

     if(flag) return;

     int i;

     if(x==)

     {

         if(judge(ss[]-,ss[]-,ss[]-,ss[]-,ss[]-)) {flag=;strcpy(res,ss);}

         return;

     }

     int l=strlen(s);

     for(i=;i<l;i++)

     {

         if(!vis[i])

         {

             vis[i]=;

             ss[x]=s[i];

             dfs(x+);

             vis[i]=;

         }

     }

 }

 int main()

 {

     int i;

     //freopen("a.txt","r",stdin);

     while(scanf("%d %s",&k,s)!=EOF&&k!=&&strcmp(s,"END")!=)

     {

         flag=;

         sort(s,s+strlen(s),cmp);

         memset(vis,,sizeof(vis));

         dfs();

         if(flag)

         {

             printf("%s\n",res);

         }

         else printf("no solution\n");

     }

     return ;

 }