深搜或者广搜都可以啦，这个题和一般的深搜广搜不同的是同一个格子能多次经过，记录状态的时候要加上当前已经打了的小怪物的数目和距离就ok了。。。。+点剪枝上去应该问题就不大了

跟重要的是要纪录图吧.
不同的路线导致打的怪也不一样.

图有什么难记录的？

那个提高的第一题用 广度优先搜索+剪枝(去重复路径,去已走过的方式,去状态相同),10S的时间应该够用,不过有可能空间不足

恩.
我就是保存图的时候空间不足了..

。。。。。终于过了。。。。我太白痴了。。。这么简单的题都要做那么久

其实这题搜索不难，但是题目不错。。。

代码的内聚搞的不好,很多耦合,不过算是出来了:

#include<stdio.h>
#include<string.h>
/*
'.'代表没有怪物,'o'代表有小怪,'O'代表大怪,'#'代表的是不能走的石头
*/
struct
{
char mapnow[8][8];
char small;
char x,y;
char l;
} line[150000]={0};
int linenow=0;
int maxline=1;
int main(void)
{
int m,mm,n,nn,k;
int i,j;
scanf("%d%d%d",&m,&n,&k);
for(i=0;i<m;i++) scanf("%s",line[linenow].mapnow[i]);
if(line[linenow].mapnow[0][0]=='o') line[linenow].small++;
if(line[linenow].mapnow[0][0]=='O')
if(k==0) line[linenow].small++; else { printf("-1"); return 0; }
if(line[linenow].mapnow[0][0]=='#') { printf("-1"); return 0; }
line[linenow].mapnow[0][0]='.';
line[linenow].x=0;
line[linenow].y=0;
line[linenow].l++;
if(line[linenow].x==m && line[linenow].y==n) { printf("1"); return 0; }
mm=m-1;
nn=n-1;
for(linenow=0;linenow<maxline;linenow++)
{
if(line[linenow].x<mm)
{
if(line[linenow].mapnow[line[linenow].x+1][line[linenow].y]=='o')
{
line[maxline]=line[linenow];
line[maxline].x++;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].small++;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); return 0; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x+1][line[linenow].y]=='.')
{
line[maxline]=line[linenow];
line[maxline].x++;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); return 0; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x+1][line[linenow].y]=='O' && line[linenow].small>=k)
{
line[maxline]=line[linenow];
line[maxline].x++;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
}
if(line[linenow].x>0)
{
if(line[linenow].mapnow[line[linenow].x-1][line[linenow].y]=='o')
{
line[maxline]=line[linenow];
line[maxline].x--;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].small++;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x-1][line[linenow].y]=='.')
{
line[maxline]=line[linenow];
line[maxline].x--;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x-1][line[linenow].y]=='O' && line[linenow].small>=k)
{
line[maxline]=line[linenow];
line[maxline].x--;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
}
if(line[linenow].y<nn)
{
if(line[linenow].mapnow[line[linenow].x][line[linenow].y+1]=='o')
{
line[maxline]=line[linenow];
line[maxline].y++;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].small++;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x][line[linenow].y+1]=='.')
{
line[maxline]=line[linenow];
line[maxline].y++;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x][line[linenow].y+1]=='O' && line[linenow].small>=k)
{
line[maxline]=line[linenow];
line[maxline].y++;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
}
if(line[linenow].y>0)
{
if(line[linenow].mapnow[line[linenow].x][line[linenow].y-1]=='o')
{
line[maxline]=line[linenow];
line[maxline].y--;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].small++;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x][line[linenow].y-1]=='.')
{
line[maxline]=line[linenow];
line[maxline].y--;
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
else
if(line[linenow].mapnow[line[linenow].x][line[linenow].y-1]=='O' && line[linenow].small>=k)
{
line[maxline]=line[linenow];
line[maxline].y--;
line[maxline].mapnow[line[maxline].x][line[maxline].y]='.';
line[maxline].l++;
if(line[maxline].x==mm && line[maxline].y==nn) { printf("%d",line[maxline].l); goto end; }
//printf("%d ",line[maxline].l);
maxline++;
}
}
if(maxline>100000) { printf("-1"); goto end; }
}
end:
return 0;
}

楼上的明显不会通过。。。

提交了,时间为0...Wrong answer...为什么?