裸BFS。
1 /* 2645 */ 2 #include <iostream> 3 #include <queue> 4 #include <cstdio> 5 #include <cstring> 6 #include <cstdlib> 7 using namespace std; 8 9 #define MAXN 200 10 11 typedef struct node_t { 12 int x, y; 13 node_t() {} 14 node_t(int xx, int yy) { 15 x = xx; y = yy; 16 } 17 } node_t; 18 19 int n, m; 20 queue<node_t> Q; 21 char map[MAXN][MAXN]; 22 int dist[MAXN][MAXN]; 23 int dir[4][2] = { 24 -1,0,1,0,0,-1,0,1 25 }; 26 27 void bfs() { 28 int i, j, k; 29 int x, y; 30 node_t nd; 31 32 while (!Q.empty()) { 33 nd = Q.front(); 34 Q.pop(); 35 for (i=0; i<4; ++i) { 36 x = nd.x + dir[i][0]; 37 y = nd.y + dir[i][1]; 38 if (x<0 || x>=n || y<0 || y>=m || map[x][y]=='1') 39 continue; 40 map[x][y] = '1'; 41 dist[x][y] = dist[nd.x][nd.y] + 1; 42 Q.push(node_t(x, y)); 43 } 44 } 45 } 46 47 int main() { 48 int i, j, k; 49 50 #ifndef ONLINE_JUDGE 51 freopen("data.in", "r", stdin); 52 #endif 53 54 while (scanf("%d %d", &n, &m) != EOF) { 55 for (i=0; i<n; ++i) { 56 scanf("%s", map[i]); 57 for (j=0; j<m; ++j) { 58 if (map[i][j] == '1') { 59 Q.push(node_t(i, j)); 60 dist[i][j] = 0; 61 } 62 } 63 } 64 bfs(); 65 for (i=0; i<n; ++i) { 66 printf("%d", dist[i][0]); 67 for (j=1; j<m; ++j) 68 printf(" %d", dist[i][j]); 69 printf(" "); 70 } 71 } 72 73 return 0; 74 }