「BZOJ1295」[SCOI2009] 最长距离
Description
windy有一块矩形土地，被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B，就没有距离。 如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。 如果windy可以移走T块障碍物，求所有格子间的最大距离。 保证移走T块障碍物以后，至少有一个格子不含有障碍物。
Input
输入文件maxlength.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，’0’表示空格子，’1’表示该格子含有障碍物。
Output
输出文件maxlength.out包含一个浮点数，保留6位小数。
Sample Input
「输入样例一」
3 3 0
001
001
110
3 3 0
001
001
110
「输入样例二」
4 3 0
001
001
011
000
「输入样例三」
3 3 1
001
001
001
Sample Output
「输出样例一」
1.414214
1.414214
「输出样例二」
3.605551
「输出样例三」
2.828427
HINT
20%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 0 。
40%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 2 。
100%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 30 。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; int n,m,T; double ans=0; bool mp[31][31],inq[31][31]; int dis[31][31]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; struct data{ int x,y; }q[100000]; void getans(int x,int y) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(dis[i][j]<=T&&sqrt((y-j)*(y-j)+(x-i)*(x-i))>ans) ans=sqrt((y-j)*(y-j)+(x-i)*(x-i)); } void search(int xx,int yy) { int t=1,w=1; q[1].x=xx;q[1].y=yy; memset(inq,0,sizeof(inq)); memset(dis,127,sizeof(dis)); inq[xx][yy]=1; dis[xx][yy]=mp[xx][yy]; while(t<=w) { int x=q[t].x,y=q[t].y;t++; inq[x][y]=0; for(int i=0;i<4;i++) if(x+dx[i]&&x+dx[i]<=n&&y+dy[i]<=m&&y+dy[i]) if(mp[x+dx[i]][y+dy[i]]&&dis[x][y]+1<dis[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]]=dis[x][y]+1; if(!inq[x+dx[i]][y+dy[i]]) { inq[x+dx[i]][y+dy[i]]=1; q[++w].x=x+dx[i]; q[w].y=y+dy[i]; } } else if(!mp[x+dx[i]][y+dy[i]]&&dis[x][y]<dis[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]]=dis[x][y]; if(!inq[x+dx[i]][y+dy[i]]) { inq[x+dx[i]][y+dy[i]]=1; q[++w].x=x+dx[i]; q[w].y=y+dy[i]; } } } getans(xx,yy); } int main() { scanf("%d%d%d",&n,&m,&T); string str; for(int i=1;i<=n;i++) { cin>>str; for(int j=0;j<m;j++) mp[i][j+1]=str[j]-'0'; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) search(i,j); printf("%.6lf",ans); return 0; } |
再打了一遍。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; int n,m,T; double ans=0; bool mp[31][31],inq[31][31],vis[31][31]; int dis[31][31]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; struct data{ int x,y; }q[100000]; void getans(int x,int y) { for(int i=x;i<=n;i++) for(int j=1;j<=m;j++) if(dis[i][j]<=T&&(y-j)*(y-j)+(x-i)*(x-i)>ans) ans=(y-j)*(y-j)+(x-i)*(x-i); } void search(int xx,int yy) { int nowx,nowy,i,t=1,w=1,nx,ny; q[1].x=xx;q[1].y=yy; memset(inq,0,sizeof(inq)); memset(dis,127,sizeof(dis)); inq[xx][yy]=1;dis[xx][yy]=mp[xx][yy]; while(t<=w) { nowx=q[t].x;nowy=q[t].y; t++; for(i=0;i<4;i++) { nx=nowx+dx[i];ny=nowy+dy[i]; if(nx>n||nx<xx||ny>m||ny<1)continue; if(dis[nowx][nowy]+mp[nx][ny]<dis[nx][ny]) { dis[nx][ny]=dis[nowx][nowy]+mp[nx][ny]; if(!inq[nx][ny]) { q[++w].x=nx;q[w].y=ny;inq[nx][ny]=1; } } } inq[nowx][nowy]=0; } getans(xx,yy); } int main() { scanf("%d%d%d",&n,&m,&T); char str[40]; for(int i=1;i<=n;i++) { scanf("%s",str); for(int j=0;j<m;j++) mp[i][j+1]=str[j]-'0'; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {search(i,j);} printf("%.6lf",sqrt(ans)); return 0; } |
计数器 9316600
OI 课件=>
OI 课件=>
第36行为什么有一个nx<xx跳过啊？不能往上走吗？
重打的那个