Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <cmath>
- #include <cstdlib>
- #include <typeinfo>
- std::ifstream FileIn ("/home/habkaffee/Cpp/Islands/input.txt");
- //std::ofstream FileOut ("/home/habkaffee/Cpp/Islands/out.txt");
- long change (long cnt, std::vector<std::vector<long>> &array, long max, long min, int n){
- for (size_t i = 0; i<n ; ++i){
- if (array[0][i] == max){
- array[0][i] = min;
- }
- if (array[1][i] == max){
- array[1][i] = min;
- }
- }
- cnt++;
- return cnt;
- }
- int main(){
- int n = 0;
- FileIn >> n;
- std::vector<std::vector<long>> array (2,std::vector<long>(n,0));
- // std::cout << n;
- char temp = 0;
- for (size_t i = 0; i<n; ++i){
- FileIn >> temp;
- array[0][i] = temp == 'x' ? 0 : -1;
- }
- // std::cout<<std::endl;
- long counter = 0; //total num of islands.
- long cnt = 0; //total num of changed islands.
- for (size_t i = 0; i<n;++i){
- if (array[0][i] == 0){
- array[0][i] = counter+1;
- if (i>0){
- if (array[0][i-1] > 0){
- array[0][i] = array[0][i-1];
- }
- }
- if (array[0][i] == counter+1){
- counter++;
- }
- }
- }
- for (int k = 1; k<n; k++){
- for (size_t i = 0; i<n; ++i){
- FileIn >> temp;
- array[1][i] = temp == 'x' ? 0 : -1;
- }
- for (size_t i = 0; i<n; ++i){
- if (array[1][i] == -1){
- continue;
- }
- else if (array[1][i] == 0){
- if (i > 0 && array[0][i]>0 && array[1][i-1]>0 && array[0][i] != array[1][i-1]){
- array[1][i] = std::min(array[0][i], array[1][i-1]);
- long a = std::max(array[0][i], array[1][i-1]);
- cnt = change (cnt, array, a, array[1][i], n);
- }
- else if (array[0][i]>0){
- array[1][i] = array[0][i];
- }
- else if (i>0 && array[1][i-1]>0) {
- array[1][i] = array[1][i-1];
- }
- else{
- counter++;
- array[1][i] = counter;
- }
- }
- }
- array[0] = array[1];
- for (size_t i = 0; i<n;++i){
- array[1][i] = 0;
- }
- }
- std::cout<<counter-cnt<<std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement