bzoj1295: [SCOI2009]最长距离

bfs最短路。

写的真丑。。。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<iostream>

using namespace std;

const int maxn = 50;

const int INF = 0x3f3f3f3f;

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

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

int n,m,T;

int a[maxn][maxn],id[maxn][maxn],vid;

char s[maxn];

int xx,x2,yy,y2,h,d[1000][maxn][maxn];

int ans;

double res;

struct Point {

    int x,y;

} q[1000];

void bfs(int x,int y) {

    h=id[x][y]=++vid;

    int l=0,r=1;

    q[0].x=x; q[0].y=y;

    if(a[x][y]) d[h][x][y]=1;

    else d[h][x][y]=0;

    while(l<r) {

        xx=q[l].x,yy=q[l].y; l++;

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

            x2=xx+dx[i];

            y2=yy+dy[i];

            if(x2<1 || x2>n || y2<1 || y2>m) continue;

            if(a[x2][y2]) {

                if(d[h][x2][y2] > d[h][xx][yy]+1) {

                    d[h][x2][y2]=d[h][xx][yy]+1;

                    if(d[h][x2][y2]<=T) {

                        q[r].x=x2;

                        q[r].y=y2;

                        r++;

                    }

                }

            }

            else if(d[h][x2][y2]>d[h][xx][yy]) {

                d[h][x2][y2]=d[h][xx][yy];

                if(d[h][x2][y2]<=T) {

                    q[r].x=x2;

                    q[r].y=y2;

                    r++;

                }

            }

        }

    }

}

inline int sqr(int x) {

    return x*x;

}

int cal(int x1,int y1,int x2,int y2) {

    return sqr(x1-x2)+sqr(y1-y2);

}

int main() {

    memset(d,0x3f,sizeof(d));

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

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

        scanf("%s",s+1);

        for(int j=1;j<=m;j++) if(s[j]=='1') a[i][j]=1;

        else a[i][j]=0;

    }

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

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

        bfs(i,j);

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

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

        h=id[i][j];

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

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

            if(d[h][x][y]<=T) ans=max(ans,cal(i,j,x,y));

    }

    res=sqrt(ans);

    printf("%0.6f\n",res);

    return 0;

}