BZOJ2252: [2010Beijing wc]矩阵距离

时间：2023-12-16 12:43:56

题解：

我脑子里都是翔？？？

bfs一下就行了 我居然还想什么kd tree！真是too naive，，，

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000+5

 #define maxm 200000+5

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)

 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,d[maxn][maxn];

 queue<pa>q;

 bool v[maxn][maxn];

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

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

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();

     for5(n,m)d[i][j]=inf;

     for5(n,m)

     {

         char ch=getchar();

         while(ch!=''&&ch!='')ch=getchar();

         if(ch==''){d[i][j]=;q.push(pa(i,j));}

     }

     while(!q.empty())

     {

         int x=q.front().first,y=q.front().second;q.pop();

         for0(i,)

         {

             int xx=x+dx[i],yy=y+dy[i];

             if(xx<||xx>n||yy<||yy>m||d[xx][yy]<=d[x][y])continue;

             d[xx][yy]=d[x][y]+;

             if(!v[xx][yy]){v[xx][yy]=;q.push(pa(xx,yy));}

         }

     }

     for1(i,n){for1(j,m)printf("%d ",d[i][j]);printf("\n");}

     return ;

 }  
 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 2000000+5

 #define maxm 200000+5

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)

 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,a[][],ans,rt,tot;

 struct rec

 {

     int d[],mi[],mx[],l,r;

     int& operator[](int i){return d[i];}

 }now,t[maxn];

 inline void pushup(int k)

 {

     int l=t[k].l,r=t[k].r;

     for0(i,)

     {

         t[k].mi[i]=min(t[k].mi[i],min(t[l].mi[i],t[r].mi[i]));

         t[k].mx[i]=max(t[k].mx[i],max(t[l].mx[i],t[r].mx[i]));

     }

 }

 inline void insert(int &k,int dir)

 {

     if(!k)

     {

         k=++tot;t[tot]=now;

         for0(i,)t[tot].mi[i]=t[tot].mx[i]=t[tot][i];

         return;

     }

     if(now[dir]<t[k][dir])insert(t[k].l,dir^);else insert(t[k].r,dir^);

     pushup(k);

 }

 inline int dist(rec a,rec b){return abs(a[]-b[])+abs(a[]-b[]);}

 inline int get(int k)

 {

     if(!k)return inf;

     int ret=;

     for0(i,)

     {

         if(now[i]<t[k].mi[i])ret+=t[k].mi[i]-now[i];

         if(now[i]>t[k].mx[i])ret+=now[i]-t[k].mx[i];

     }

     return ret;

 }

 inline void query(int k,int dir)

 {

     int dl=get(t[k].l),dr=get(t[k].r),d0=dist(t[k],now);

     if(d0<ans)ans=d0;

     if(dl<dr)

     {

         if(dl<ans)query(t[k].l,dir^);

         if(dr<ans)query(t[k].r,dir^);

     }else

     {

         if(dr<ans)query(t[k].r,dir^);

         if(dl<ans)query(t[k].l,dir^);

     }

 }

 int b[];

 inline void print(int x)

 {

    if(!x)putchar('');

    for(b[]=;x;x/=)b[++b[]]=x%;

    for3(i,b[],)putchar(''+b[i]);

 }   

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();

     for1(i,n)for1(j,m)

     {

         char ch=getchar();

         while(ch!=''&&ch!='')ch=getchar();

         a[i][j]=ch-'';

         if(ch==''){now[]=i;now[]=j;insert(rt,);}

     }

     for1(i,n)

     {

         for1(j,m)

         {

             if(j!=)putchar(' ');

             if(a[i][j]==)putchar('');

             else {now[]=i;now[]=j;ans=inf;query(rt,);print(ans);}

         }

         printf("\n");

     }

     return ;

 }

2252: [2010Beijing wc]矩阵距离

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 529  Solved: 255
[Submit][Status]

Description

假设我们有矩阵,其元素值非零即1

a11…… a1m

…………….

an1…….anm

定义aij与akl之间的距离为D(aij,akl)=abs(i-k)+abs(j-L) 

Input

输入文件的第一行为两个整数，分别代表n和m。
接下来的n行，第i行的第 j个字符代表aij

Output

输出包含N行，每行M个用空格分开的数字，其中第i行第J个数字代表
Min(D(aij,axy) 1<=x<=N 1<=y<m,且axy=1

Sample Input

3 4
0001
0011
0110

Sample Output

3 2 1 0
2 1 0 0
1 0 0 1

HINT

对于100%的数据，满足 0 <  m n <=1000

相关文章