偶也不知啊!!
我继续改...

俺觉得这个题不用搜索貌似也能解决,而且将原题的数据量再扩大100倍应该也可以搞定.

所有解答已公开，leeco解答出两个题目，解答数最多，获得冠军



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

你总算是醒过来了...
搜索那个题目够郁闷的..还是过不去..

怎么做？如果不搜的话？

我的想法是这样的:
先分两种情况:
1.需要经过big monster
2.不需要经过big monster
对于第二种情况,可以将big monster当作障碍物,small monster当作empty room处理,直接求0,0到height-1,width-1的最短路径.
此时有现成的算法(用队列,事件复杂度为O(width*height))得到这个值
对于第一种情况,分两步:
第一步计算从起点出发经历num(num只升级需要打小怪的个数)个小怪最少要走的路程(此时将大怪视为障碍物),这个路线是以某个小怪为终点.(可以用动态规划求之...或许有其它算法)
第二步计算从小怪出发到达终点的最短路程(此时将大怪视为empty room)(可以用上面说的那种算法)
这两步的总和的最小值与第二种情况比较就可以得到全局最小值.

第一步计算从起点出发经历num(num只升级需要打小怪的个数)个小怪最少要走的路程(此时将大怪视为障碍物),这个路线是以某个小怪为终点.(可以用动态规划求之...或许有其它算法)

你想清楚这个再说啦。。。。

eastsun.大哥..
我刚开始的想法就是和你差不多.
我写了两个bfs.
第一个bfs算从起点经过num个小怪之后到达的地方..保存到数组中.
然后在从数组中找哪些地方是可以的在bfs.结果写了3KB.还RE了

这是我几天前写的.和eastsun的思路差不多.他居然也是个WA.
WA其实还是有希望的.实在也改不出来了


#include<stdio.h>
#include<set>
using namespace std;
typedef long long int64;
set<int64> mp[10][10];
int n,m,k;
struct node
{
int64 a1;
int x,y,n;
}a[100000];

struct Node
{
int x,y;
}q[200];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char s[10][10];
int check(int x,int y,int64 &temp)
{
int64 i=1;
i<<=(x*n+y);
if(temp&i) return 0;
temp=temp|i;
return 1;
}
int flag[10][10];
void bfs()
{
int i=0,j=2,p,x,y;
int64 temp;
int ans=1;
a[0].x=a[0].y=a[0].a1=0;
if(s[0][0]=='o')
{
a[0].n=1;
s[0][0]='.';
a[0].a1=1;
}
mp[0][0].insert(a[0].a1);
a[1].x=-1;
while(1)
{
if(a[i].x==-1)
{
if(j==i+1) return ;
else
{
a[j++].x=-1;
ans++;
}
}
else
{
if(a[i].x==n-1&&a[i].y==m-1)
{
flag[n-1][m-1]=ans;
return;
}
else
{
for(p=0;p<4;p++)
{
x=a[i].x+dx[p];
y=a[i].y+dy[p];
if((x>=0&&x<n)&&(y>=0&&y<m))
{
temp=a[i].a1;
if(s[x][y]=='.'||s[x][y]=='o')
{
if(mp[x][y].find(temp)==mp[x][y].end())
{
a[j].x=x;
a[j].y=y;
a[j].n=a[i].n;
mp[x][y].insert(temp);
if(s[x][y]=='o')
{
if(check(x,y,temp))
a[j].n++;
}
a[j].a1=temp;
mp[x][y].insert(temp);
j++;
}
}
else if(s[x][y]=='O')
{
if(a[i].n>=k&&!flag[x][y])
{
flag[x][y]=ans;
}
}
}
}
}
}
i++;
}
}
int bfs2(int xx,int yy)
{
int i=0,j=2,ans=0,p,x,y;
bool flg[10][10]={0};
flg[xx][yy]=1;
q[0].x=xx;
q[0].y=yy;
q[1].x=-1;
while(i<j)
{
if(q[i].x==-1)
{
if(i+1==j) return -1;
else
{
q[j++].x=-1;
ans++;
}
}
else
{
if(q[i].x==n-1&&q[i].y==m-1)
{
return flag[xx][yy]+ans+1;
}
else
{
for(p=0;p<4;p++)
{
x=q[i].x+dx[p];
y=q[i].y+dy[p];
if((x>=0&&x<n)&&(y>=0&&y<m))
{
if(!flg[x][y]&&s[x][y]!='#')
{
q[j].x=x;
q[j].y=y;
j++;
flg[x][y]=1;
}
}
}
}
}
i++;
}
return -1;
}
int main()
{
int i,j,ans,temp;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%s",s[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
mp[i][j].clear();
flag[i][j]=0;
}
}
if(s[0][0]=='O')
{
if(k==0)
{
printf("%d\n",bfs2(0,0));
}
else printf("-1\n");
}
else if(s[0][0]=='#') printf("-1\n");
else
{
bfs();
/* for(i=0;i<n;i++)
{
for(j=0;j<m;j++) printf("%d",flag[i][j]);
printf("\n");
} */
if(flag[n-1][m-1]) ans=flag[n-1][m-1]+1;
else ans=-1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(flag[i][j])
{
temp=bfs2(i,j);
if(temp!=-1)
{
if(ans==-1) ans=temp;
else ans=ans>temp?temp:ans;
}
}
}
}
printf("%d\n",ans);
}
}
return 0;
}

[此贴子已经被作者于2007-9-15 22:35:19编辑过]

2 2 0
..
.O

4 4 3
o...
....
o..o
o#OO

你的输出好像差1吧