fork(8) download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <time.h>
  7. #include <queue>
  8. #define mod 1000000000
  9. #define ll long long int
  10.  
  11. using namespace std;
  12.  
  13. class point
  14. {
  15.     public:
  16.         int x, y, z;
  17.     point(int i, int j, int k)
  18.     {
  19.         x = i;
  20.         y = j;
  21.         z = k;
  22.     }
  23. };
  24.  
  25. int n, m;
  26. int grid[200][200];
  27. char board[200][200];
  28.  
  29. int dx[] = {1, -1, 0, 0};
  30. int dy[] = {0, 0, 1, -1};
  31. int iterations;
  32.  
  33. void BFS(queue <point> bfs)
  34. {
  35.     int i, j, x, y;
  36.     point temp(0,0,0);
  37.     while(!bfs.empty())
  38.     {
  39.         temp = bfs.front();
  40.         bfs.pop();
  41.         grid[temp.x][temp.y] = temp.z;
  42.  
  43. 		// if the adjacent cells are unvisited, pushing it onto the queue.
  44.         for(i=0; i<4; i++)
  45.         {
  46. 			iterations++;
  47.             x = temp.x+dx[i];
  48.             y = temp.y+dy[i];
  49.             if(grid[x][y]==-1)
  50.                 bfs.push(point(x,y,temp.z+1));
  51.         }
  52.     }
  53.     for(i=0; i<n; i++)
  54.     {
  55.         for(j=0; j<m; j++)
  56.             printf("%d ", grid[i][j]);
  57.         printf("\n");
  58.     }
  59. 	cout << "number of iterations : " << iterations << endl;
  60. }
  61.  
  62. int main()
  63. {
  64.     int t, i, j;
  65.     scanf("%d", &t);
  66.     while(t--)
  67.     {
  68.         queue <point> bfs;
  69.  
  70.         // taking input
  71.         scanf("%d %d", &n, &m);
  72.         for(i=0; i<n; i++)
  73.             scanf("%s", board[i]);
  74.  
  75. 		// putting the value for each point to be -1
  76.         for(i=0; i<n; i++)
  77.             for(j=0; j<m; j++)
  78.             grid[i][j] = -1;
  79.  
  80.         for(i=0; i<n; i++)
  81.         {
  82.             for(j=0; j<m; j++)
  83.             {
  84.             	// if the point is white, putting its value to be 1, and pushing it onto the queue
  85.                 if(board[i][j]=='1')
  86.                 {
  87.                     grid[i][j] = 0;
  88.                     bfs.push(point(i,j,0));
  89.                 }
  90.             }
  91.         }
  92. 		iterations=0;
  93.         BFS(bfs);
  94.     }
  95.     return 0;
  96. }
  97.  
  98.  
Success #stdin #stdout 0.01s 3672KB
comments (?)
stdin
copy 
1
10 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000001
stdout
copy 
18 17 16 15 14 13 12 11 10 9 
17 16 15 14 13 12 11 10 9 8 
16 15 14 13 12 11 10 9 8 7 
15 14 13 12 11 10 9 8 7 6 
14 13 12 11 10 9 8 7 6 5 
13 12 11 10 9 8 7 6 5 4 
12 11 10 9 8 7 6 5 4 3 
11 10 9 8 7 6 5 4 3 2 
10 9 8 7 6 5 4 3 2 1 
9 8 7 6 5 4 3 2 1 0 
number of iterations : 739020
https://ideone.com/JMF44l
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!