Advertisement
Riposati

Untitled

Jun 22nd, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 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.         for (j = 0; j < m; j++) {
  49.  
  50.             scanf("%c",&mapa[i][j]);
  51.         }
  52.     }
  53.  
  54.     int ans=0;
  55.  
  56.         for (i = 0; i < n; i++) {
  57.  
  58.             for (j = 0; j < m; j++) {
  59.  
  60.                 if (mapa[i][j]=='.') {
  61.  
  62.                     ans++;
  63.                     backtracking(i, j);
  64.                 }
  65.             }
  66.         }
  67.  
  68.         printf("%d\n",ans);
  69.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement