Advertisement
HabKaffee

Untitled

Nov 15th, 2020
144
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <cmath>
  5. #include <cstdlib>
  6. #include <typeinfo>
  7.  
  8. std::ifstream FileIn ("/home/habkaffee/Cpp/Islands/input.txt");
  9. //std::ofstream FileOut ("/home/habkaffee/Cpp/Islands/out.txt");
  10.  
  11. long change (long cnt, std::vector<std::vector<long>> &array, long max, long min, int n){
  12.     for (size_t i = 0; i<n ; ++i){
  13.         if (array[0][i] == max){
  14.             array[0][i] = min;
  15.         }
  16.         if (array[1][i] == max){
  17.             array[1][i] = min;
  18.         }
  19.     }
  20.     cnt++;
  21.     return cnt;
  22. }
  23.  
  24. int main(){
  25.     int n = 0;
  26.     FileIn >> n;
  27.     std::vector<std::vector<long>> array (2,std::vector<long>(n,0));
  28.  
  29. //    std::cout << n;
  30.  
  31.     char temp = 0;
  32.  
  33.     for (size_t i = 0; i<n; ++i){
  34.         FileIn >> temp;
  35.         array[0][i] = temp == 'x' ? 0 : -1;
  36.     }
  37.  
  38.    // std::cout<<std::endl;
  39.     long counter = 0; //total num of islands.
  40.     long cnt = 0; //total num of changed islands.
  41.  
  42.     for (size_t i = 0; i<n;++i){
  43.         if (array[0][i] == 0){
  44.             array[0][i] = counter+1;
  45.             if (i>0){
  46.                 if (array[0][i-1] > 0){
  47.                     array[0][i] = array[0][i-1];
  48.                 }
  49.             }
  50.             if (array[0][i] == counter+1){
  51.                 counter++;
  52.             }
  53.         }
  54.     }
  55.  
  56.  
  57.     for (int k = 1; k<n; k++){
  58.         for (size_t i = 0; i<n; ++i){
  59.             FileIn >> temp;
  60.             array[1][i] = temp == 'x' ? 0 : -1;
  61.         }  
  62.  
  63.         for (size_t i = 0; i<n; ++i){
  64.             if (array[1][i] == -1){
  65.                 continue;
  66.             }
  67.             else if (array[1][i] == 0){
  68.                 if (i > 0 && array[0][i]>0 && array[1][i-1]>0 && array[0][i] != array[1][i-1]){
  69.                     array[1][i] = std::min(array[0][i], array[1][i-1]);
  70.                     long a = std::max(array[0][i], array[1][i-1]);
  71.                     cnt = change (cnt, array, a, array[1][i], n);
  72.                 }
  73.                 else if (array[0][i]>0){
  74.                     array[1][i] = array[0][i];
  75.                 }
  76.                 else if (i>0 && array[1][i-1]>0) {
  77.                     array[1][i] = array[1][i-1];
  78.                 }
  79.                 else{
  80.                     counter++;
  81.                     array[1][i] = counter;
  82.  
  83.                 }
  84.             }
  85.         }
  86.  
  87.         array[0] = array[1];
  88.         for (size_t i = 0; i<n;++i){
  89.             array[1][i] = 0;
  90.         }
  91.     }
  92.  
  93.     std::cout<<counter-cnt<<std::endl;
  94.  
  95.     return 0;
  96.  
  97. }
Advertisement
RAW Paste Data Copied
Advertisement