8 8 5
oo....oO
....Oo.o
o.OOO...
o#O.#.#.
oo....oO
....Oo.o
o.OOO...
o#O.#.#.

这个数据是不是15?
我也开始WA了

要用double.pi=acos(-1)..

是不是有什么trick.我一直WA.
还有我的程序对这组数据明显超时
8 8 100
oooooooo
oooooooo
oooooooo
oooooooo
oooooooo
oooooooo
oooooooo
oooooooO

#include<stdio.h>
int b[10][10];
int n,m,k,ans,flag;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
char s[10][10];

void dfs(int x,int y,int kk,int path)
{
int temp,i,j,xx,yy;
char ch;
if(x==n-1&&y==m-1)
{
if(flag)
{
ans=path;
flag=0;
}
else ans=ans>path?path:ans;
}
if(ans!=-1&&path>=ans) return ;
for(i=0;i<4;i++)
{
xx=dx[i]+x;
yy=dy[i]+y;
if(xx>=0&&xx<n&&yy>=0&&yy<m)
{
if(s[xx][yy]=='.'&&b[xx][yy]<kk)
{
temp=b[xx][yy];
b[xx][yy]=kk;
dfs(xx,yy,kk,path+1);
b[xx][yy]=temp;
}
else if(s[xx][yy]=='o')
{
b[xx][yy]=kk+1;
s[xx][yy]='.';
dfs(xx,yy,kk+1,path+1);
s[xx][yy]='o';
b[xx][yy]=0;
}
else if(s[xx][yy]=='O'&&kk>=k)
{
b[xx][yy]=kk+1;
s[xx][yy]='.';
dfs(xx,yy,kk+1,path+1);
b[xx][yy]=0;
s[xx][yy]='O';
}
}
}
}
int main()
{
int i,j;
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++) b[i][j]=0;
}
ans=-1;
flag=1;
if(s[0][0]=='o')
{
s[0][0]='.';
b[0][0]=1;
dfs(0,0,1,1);
}
else if(s[0][0]=='O')
{
if(k==0)
{
s[0][0]='.';
b[0][0]=1;
dfs(0,0,1,1);
}
else ans=-1;
}
else if(s[0][0]=='#') ans=-1;
else dfs(0,0,0,1);
printf("%d\n",ans);
}
return 0;
}

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

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

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编辑过]

晕.
不只你这两组错误数据太多了.继续改.就不信了

我和你有点不同.我是把打了k个怪保存在'O'上.
我尝试一下把它保存到'o'上看看

是DI