Advertisement
Riposati

Untitled

Jun 23rd, 2016
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. #define MAX 1030
  8.  
  9.     char mapa[MAX][MAX];
  10.     int n, m;
  11.  
  12.     int dx[4] = {1,-1,0,0};
  13.     int dy[4] = {0,0,-1,1};
  14.  
  15.     bool inGrid(int i, int j) {
  16.  
  17.         if (i < 0 || i >= n || j < 0 || j >= m) {
  18.  
  19.             return false;
  20.         }
  21.  
  22.         return (mapa[i][j] == '.');
  23.     }
  24.  
  25.     void backtracking(int i, int j) {
  26.  
  27.         mapa[i][j] = 'o';
  28.  
  29.         int x;
  30.  
  31.         for (x = 0; x < 4; x++) {
  32.  
  33.             if (inGrid(i + dx[x], j + dy[x])) {
  34.  
  35.                 backtracking(i + dx[x], j + dy[x]);
  36.             }
  37.         }
  38.     }
  39.  
  40. int main()
  41. {
  42.     int i,j;
  43.  
  44.     scanf("%d %d",&n,&m);
  45.  
  46.     for (i = 0; i < n; i++) {
  47.  
  48.             scanf("%s",&mapa[i]);
  49.             getchar();
  50.     }
  51.  
  52.     int ans=0;
  53.  
  54.         for (i = 0; i < n; i++) {
  55.  
  56.             for (j = 0; j < m; j++) {
  57.  
  58.                 if (mapa[i][j]=='.') {
  59.  
  60.                     ans++;
  61.                     backtracking(i, j);
  62.                 }
  63.             }
  64.         }
  65.  
  66.         printf("%d\n",ans);
  67.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement