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 ;
}