【BZOJ】2252: [2010Beijing 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

Sample Output

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

HINT

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

题解：

  题目描述的符号并没有看懂是什么啊。。好像是不同的位置的这个符号代表不同的含义。。有兴趣的童鞋可以复制之后粘贴到word里面看一看……

  直接bfs……

  千万注意不能过滤行末空格……我过滤了然后我PE了。。。于是就这样吧。。。

 

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int MAXN = 1001; int dist[MAXN][MAXN]; int n, m; int mx[] = { 0, 0, -1, 1 }; int my[] = { 1, -1, 0, 0 }; char g[MAXN][MAXN]; bool check(int x, int y) { if (x > n || x<1 || y>m || y < 1) return false; if (dist[x][y] != -1) return false; return true; } queue <int> Q1; queue <int> Q2; void bfs() { int i, j, tx, ty; while (!Q1.empty()) { tx = Q1.front(); ty = Q2.front(); Q1.pop(); Q2.pop(); for (i = 0; i < 4; i++) { if (check(tx + mx[i], ty + my[i])) { dist[tx + mx[i]][ty + my[i]] = dist[tx][ty] + 1; Q1.push(tx + mx[i]); Q2.push(ty + my[i]); } } } } int main(int argc, char *argv[]) { int i, j; scanf("%d%d", &n, &m); memset(dist, -1, sizeof(dist)); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { cin >> g[i][j]; if (g[i][j] == '1') { Q1.push(i); Q2.push(j); dist[i][j] = 0; } } bfs(); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { printf("%d ", dist[i][j]); } puts(""); //printf("%d\n", dist[i][m]); } return 0; }