题目
2252: [2010Beijing wc]矩阵距离
Time Limit: 10 Sec Memory Limit: 256 MB
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
题解
好吧，就是一个宽搜，而且根据宽搜的性质，所以每个点只需要经过一次就足够了。
代码
/*Author:WNJXYK*/
#include<cstdio>
#include<queue>
using namespace std; int dist[][]; int n,m;
int dx[]={,,,-,};
int dy[]={,,,,-};
inline char read(){
char x;
x=getchar();
while(x!='' && x!='') x=getchar();
return x;
}
struct xy{
int x,y;
xy(){}
xy(int a,int b){
x=a;y=b;
}
};
queue<xy> que; inline void bfs(){ while(!que.empty()){
int x=que.front().x,y=que.front().y;
que.pop();
for (int k=;k<=;k++){
int nx=x+dx[k],ny=y+dy[k];
if (nx< || nx>n || ny< || ny>m || dist[nx][ny]!=-) continue;
dist[nx][ny]=dist[x][y]+;
que.push(xy(nx,ny));
}
} }
int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
if (read()=='') dist[i][j]=-; else {dist[i][j]=;que.push(xy(i,j));}
}
}
bfs();
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
printf("%d ",dist[i][j]);
}
printf("\n");
}
return ;
}