fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. #define MAX 1001
  8.  
  9. struct node
  10. {
  11.   int x;
  12.   int y;
  13.   int distance;
  14. };
  15.  
  16. int l, c;
  17. char grid[MAX][MAX], temp;
  18. node clouds[MAX * MAX];
  19. int n_clouds = 0;
  20. int i, u;
  21. int visited[MAX][MAX];
  22. int dx[] = {-1, 0, 1, 0};
  23. int dy[] = {0, -1, 0, 1};
  24. int n_min, n_max;
  25.  
  26. inline int max(int a, int b)
  27. {
  28.   return a > b ? a : b;
  29. }
  30.  
  31. inline int min(int a, int b)
  32. {
  33.   return a < b ? a : b;
  34. }
  35.  
  36. void read_input()
  37. {
  38.   scanf("%d %d", &l, &c);
  39.  
  40.   for (i = 0; i < l; i++)
  41.   {
  42.     for (u = 0; u < c; u++)
  43.     {
  44.       scanf(" %c", &temp);
  45.       grid[i][u] = temp;
  46.  
  47.       if (temp == '#')
  48.       {
  49.         node cloud;
  50.         cloud.x = u;
  51.         cloud.y = i;
  52.  
  53.         clouds[n_clouds] = cloud;
  54.         n_clouds++;
  55.       }
  56.     }
  57.   }
  58. }
  59.  
  60. void bfs(node start)
  61. {
  62.   queue<node> q;
  63.   q.push(start);
  64.  
  65.   memset(visited, 0, sizeof visited);
  66.  
  67.   while (!q.empty())
  68.   {
  69.     node current = q.front();
  70.     q.pop();
  71.  
  72.     int x = current.x;
  73.     int y = current.y;
  74.     int distance = current.distance;
  75.  
  76.     if (x < 0 || y < 0 || x >= c || y >= l || visited[y][x])
  77.     {
  78.       continue;
  79.     }
  80.  
  81.     //printf("x: %d, y: %d\n", x, y);
  82.  
  83.     visited[y][x] = 1;
  84.  
  85.     if (grid[y][x] == 'A')
  86.     {
  87.       printf("distance: %d\n", distance);
  88.  
  89.       if (n_min == -1)
  90.         n_min = distance;
  91.       else
  92.         n_min = min(n_min, distance);
  93.  
  94.       n_max = max(n_max, distance);
  95.       return;
  96.     }
  97.  
  98.     node node;
  99.     node.distance = distance + 1;
  100.  
  101.     int k;
  102.     for (k = 0; k < 4; k++)
  103.     {
  104.       node.x = x + dx[k];
  105.       node.y = y + dy[k];
  106.       q.push(node);
  107.  
  108.       //printf("node.x = %d, node.y = %d, k = %d\n", node.x, node.y, k);
  109.     }
  110.   }
  111. }
  112.  
  113. int main()
  114. {
  115.   read_input();
  116.  
  117.   n_min = -1;
  118.   n_max = -1;
  119.  
  120.   for (i = 0; i < n_clouds; i++)
  121.   {
  122.     bfs(clouds[i]);
  123.   }
  124.  
  125.   printf("%d %d\n", n_min, n_max);
  126.  
  127.   return 0;
  128. }
  129.  
Success #stdin #stdout 0.01s 19672KB
comments (?)
stdin
copy 
7 8
..#...##
.##.....
###.A..A
.#......
.#....A.
...A....
........
stdout
copy 
distance: 4
distance: 3
distance: 2
distance: 4
distance: 3
distance: 4
distance: 3
distance: 2
distance: 4
distance: 3
2 4
https://ideone.com/822Egw
language:
C++ (gcc 8.3)
created:
12 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!