「BZOJ2252」[2010BJ WC] 矩阵距离
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
0001
0011
0110
Sample Output
3 2 1 0
2 1 0 0
1 0 0 1
2 1 0 0
1 0 0 1
HINT
对于100%的数据，满足 0 < m n <=1000
题解
直接bfs
|
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 |
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int x[1000001],y[1000001]; int n,m,dis[1001][1001],t,w=1; int xx[4]={0,0,-1,1},yy[4]={1,-1,0,0}; char ch[1001]; void bfs() { while(t<w) { int i=x[t],j=y[t++]; for(int k=0;k<4;k++) { int nowx=i+xx[k],nowy=j+yy[k]; if(nowx<1||nowy<1||nowx>n||nowy>m||dis[nowx][nowy]!=-1)continue; dis[nowx][nowy]=dis[i][j]+1; x[w]=nowx;y[w++]=nowy; } } } int main() { memset(dis,-1,sizeof(dis)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",ch); for(int j=1;j<=m;j++) if(ch[j-1]=='1') { x[w]=i;y[w++]=j; dis[i][j]=0; } } bfs(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%d ",dis[i][j]); printf("\n"); } return 0; } |
Subscribe
计数器 9788181
OI 课件=>
OI 课件=>