找不到原来的帖子了。。。开了一个新贴。
原题链接 http://acm.jlu.edu.cn/joj/showproblem.php?pid=2438
题目意思大概就是从一个格子的左上角走到又下角的最小步数。如果没有其他的条件
这个就是一个很基本的搜索题目，这个题中增加了大小两种怪物，而且同一个格子能
多次经过，令题目的难度增加了不少。
有一个比较好的剪枝就是：纪录着每个格子的当前的最优值，这个最优值包括两个，
一个是经过这个格子的步数，一个是经过这个格子的时候已经杀了小怪兽的数目。
当经过一个 "." 的格子(空格子)的时候，应该判断，当前的步数是否小于这个格子纪录
的步数，或者当前已经杀的小怪兽的数目比当前纪录的小怪兽的数目大。只有这两个条件
之一成立，这一步才值得去走，其中道理大家想一想就明白的了。
有了这个剪枝，注意一点特殊的边界数据，就能解决这个题目了。
Eastsun的想法我都有想过，算法应该没错的。不知道他现在过了没？
在zju有一道比较相似的题目，剪枝的思想也和这个题目差不多
http://acm.zju.edu.cn/show_problem.php?pid=1671
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
const int inf= 10000000;char map[10][10];
int d[10][10];
int kill[10][10];
int n,m,k;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y,int &ans,int sum,int killed)
{
if(map[x][y]=='#')return ;
if(sum>=ans)return ;
if(x==n-1 && y==m-1){
if(map[x][y]!='O')ans=sum;
else if(killed>=k)ans=sum;
return ;
}
int xx,yy,i;
char tmpm=map[x][y];
int tmpd=d[x][y];
int tmpk=kill[x][y];
for(i=0;i<4;i++){
xx=x+dir[i][0];yy=y+dir[i][1];
if(xx>=0 && xx<n && yy>=0 && yy<m){
if(map[x][y]=='o'){
map[x][y]='.';
d[x][y]=sum+1;
kill[x][y]=killed+1;
dfs(xx,yy,ans,sum+1,killed+1);
map[x][y]=tmpm;
d[x][y]=tmpd;
kill[x][y]=tmpk;
}
if(map[x][y]=='O'&&killed>=k){
map[x][y]='.';
d[x][y]=sum+1;
kill[x][y]=killed;
dfs(xx,yy,ans,sum+1,killed);
d[x][y]=tmpd;
kill[x][y]=tmpk;
map[x][y]=tmpm;
}
if(map[x][y]=='.'){
if((d[x][y]>sum+1) || (kill[x][y]<killed)){
d[x][y]=sum+1;
kill[x][y]=killed;
dfs(xx,yy,ans,sum+1,killed);
d[x][y]=tmpd;
kill[x][y]=tmpk;
}
}
}
}
}
int main()
{
int i,j;
while(scanf(\"%d%d%d\",&n,&m,&k)!=EOF)
{
for(i=0;i<n;i++)scanf(\"%s\",map[i]);
for(i=0;i<n;i++)for(j=0;j<m;j++)d[i][j]=inf;
memset(kill,0,sizeof(kill));
int ans=inf;
dfs(0,0,ans,0,0);
if(ans!=inf)printf(\"%d\n\",ans+1);
else printf(\"-1\n\");
}
return 0;
}
.