fork(1) download
copy 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16.  
  17. #define MAX 200
  18. #define PRIME 31
  19. #define MOD 1000000007
  20. #define PI 3.1415926535897932384
  21. #define F first
  22. #define S second
  23. #define pb push_back
  24. #define mp make_pair
  25. typedef long long ll;
  26.  
  27. int n, m;
  28. char field[MAX][MAX];
  29. int dist[MAX][MAX];
  30.  
  31. bool valid(int a, int b){
  32.     return (a >= 0 && a < n && b >= 0 && b < m);
  33. }
  34.  
  35. void bfs(int x, int y){
  36.     queue<pair<int, pair<int, int> > > q;
  37.  
  38.     q.push(mp(0, mp(x, y)));
  39.  
  40.     while(!q.empty()){
  41.         pair<int, pair<int, int> > p = q.front();
  42.         q.pop();
  43.  
  44.         int a = p.S.F, b = p.S.S;
  45.  
  46.         if(dist[a][b] != -1 && dist[a][b] <= p.F) continue;
  47.         if(field[a][b] == '1') p.F = 0;
  48.  
  49.         dist[a][b] = p.F;
  50.  
  51.         if(valid(a+1, b) && (dist[a+1][b] == -1 || dist[a+1][b] > dist[a][b]+1)) q.push(mp(dist[a][b]+1, mp(a+1, b)));
  52.         if(valid(a, b+1) && (dist[a][b+1] == -1 || dist[a][b+1] > dist[a][b]+1)) q.push(mp(dist[a][b]+1, mp(a, b+1)));
  53.         if(valid(a-1, b) && (dist[a-1][b] == -1 || dist[a-1][b] > dist[a][b]+1)) q.push(mp(dist[a][b]+1, mp(a-1, b)));
  54.         if(valid(a, b-1) && (dist[a][b-1] == -1 || dist[a][b-1] > dist[a][b]+1)) q.push(mp(dist[a][b]+1, mp(a, b-1)));
  55.     }
  56. }
  57.  
  58. int main(){
  59.     //freopen("in.txt", "r", stdin);
  60.     int t;
  61.  
  62.     cin >> t;
  63.     while(t--){
  64.         cin >> n >> m;
  65.         memset(dist, -1, sizeof(dist));
  66.  
  67.         for(int i = 0;i < n;i++){
  68.             for(int j = 0;j < m;j++){
  69.                 scanf(" %c", &field[i][j]);
  70.             }
  71.         }
  72.  
  73.         for(int i = 0;i < n;i++){
  74.             for(int j = 0;j < m;j++){
  75.                 if(field[i][j] == '1'){ bfs(i, j); break; }
  76.             }
  77.         }
  78.  
  79.         for(int i = 0;i < n;i++){
  80.             for(int j = 0;j < m;j++){
  81.                 cout << dist[i][j] << " \n"[j == m-1];
  82.             }
  83.         }
  84.     }
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 3660KB
comments (?)
stdin
copy 
2
3 4
0001
0011
0110

4 6
100001
100001
100001
100001
stdout
copy 
3 2 1 0
2 1 0 0
1 0 0 1
0 1 2 2 1 0
0 1 2 2 1 0
0 1 2 2 1 0
0 1 2 2 1 0
https://ideone.com/FrRpPJ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!