讨论 / 70求找错
lvchaojie 2013-10-01 19:12:00
点我顶贴 收藏 删除
测试结果1: 选手程序无输出

测试结果2: 选手程序无输出

测试结果3: 通过本测试点|有效耗时109ms

测试结果4:

测试结果5: 通过本测试点|有效耗时93ms

测试结果6: 通过本测试点|有效耗时79ms

测试结果7: 通过本测试点|有效耗时93ms

测试结果8: 通过本测试点|有效耗时110ms

测试结果9: 通过本测试点|有效耗时109ms

测试结果10: 通过本测试点|有效耗时203ms

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 32

const int u[4]={1,0,-1,0};

const int v[4]={0,1,0,-1};

struct P{int x,y;}re[N*N];

char s[N];

int ans;

int n,m,T;

int map[N][N];

int value[N][N];

int sqr(int x,int y){return x*x+y*y;}

void bfs(int x0,int y0)

{

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

value[i][j]=100000;

int x,y,dx,dy;

re[1].x=x0;re[1].y=y0;

value[x0][y0]=map[x0][y0];

for (int h=1,t=1;h<=t;h++)

{

x=re[h].x,y=re[h].y;

for (int i=0;i<4;i++)

{

dx=x+u[i],dy=y+v[i];

if (0<dx && dx<=n && 0<dy && dy<=m)

if (value[dx][dy]>value[x][y]+map[dx][dy])

{

t++;re[t].x=dx;re[t].y=dy;

value[dx][dy]=value[x][y]+map[dx][dy];

}

}

}

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

if (value[i][j]<=T && sqr(i-x0,j-y0)>ans)

ans=sqr(i-x0,j-y0);

}

int main()

{

scanf("%d%d%d",&n,&m,&T);

for (int i=1;i<=n;i++)

{

scanf("%s",s);

for (int j=1;j<=m;j++)

map[i][j]=s[j-1]-'0';

}

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

bfs(i,j);

printf("%.6lf",sqrt(ans));

return 0;

}

#1 absi2011@2013-10-01 18:50:00
回复 删除
重新提交。。

RT

#2 drcool@2013-10-01 19:12:00
回复 删除
请将re[N*N] 改大比如re[200000]

请将re[N*N] 改大比如re[200000],因为有障碍点的问题,虽然是BFS访问,但是不能保证第二次访问同一个点时的value值就比第一次的大,所以,同一个点可能多次进入队列,所以N*N的队列太小,每个点可能要访问多次,我把你的程序改成re[200000],提交通过了.....

查看更多回复
提交回复