找不到原来的帖子了。。。开了一个新贴。
原题链接 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;
}
----------------解决方案--------------------------------------------------------
你总算肯把你思路说出来了....
再不说我也想问你了...
写了几天都没过..
----------------解决方案--------------------------------------------------------
那我的那个3KB两个bfs和eastsun差不多...
难道我的那个想法也没错.
可惜还是没过.
不知道是特殊数据没有考虑到还是根本就是算法是错的.
[此贴子已经被作者于2007-9-18 22:39:53编辑过]
----------------解决方案--------------------------------------------------------
其实我比较反对贴代码的。。。。但是我的思路也就是短短几句话，难登大雅之堂。。。
----------------解决方案--------------------------------------------------------
开始你提示我之后我也写了一个不过没有把步数考虑进去.结果RE了.
貌似这个题目有很奇怪的特殊数据.应该TLE的都是WA
----------------解决方案--------------------------------------------------------
这个题目数据应该没有那么恐怖。。。毕竟64个格子的搜索理论上怎么都过不去的。。。如果是考你这个理论的负责度的话，那样就没什么意思了。。。这个题的剪枝思想比较好
----------------解决方案--------------------------------------------------------
你那个bfs的做法。。。是我开始的写法。。。写了一半发现比较难纪录状态，就改成了深搜了
----------------解决方案--------------------------------------------------------
我以前也做过一个比较类似的题目,也是同一坐标可能经过多次.那个题目也是8*8.结果用64位加set就过了.所以这个题目上来一写就想到那个方法...
----------------解决方案--------------------------------------------------------