Projeto1ASA/p1.cpp at main · AVAM16/Projeto1ASA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
#include <array>
#include <ctime>
#include <ratio>
#include <chrono>

using namespace std;

unsigned int _N, _M;
vector<int> _path;
vector<array<int, 3>> _possibleSquares;

void readGraph()
{
  cin >> _N >> _M;
  _path.reserve(_N);
  _possibleSquares.reserve(_N * _M);
  for (size_t i = 0; i < _N; i++)
  {
    int a;
    cin >> a;
    _path.push_back(a);
  }
}

void findAllPossibleSquares()
{
  for (unsigned int a = 0; a < _N - 1; a++) {
    int height = _N - a;
    int length = _path.at(a);
    for (int i = 0; i < length - 1; i++) {
      for (int b = min(height, length - i); b > 1; b--) {
        array<int, 3> temp;
        temp[0] = a;
        temp[1] = i;
        temp[2] = b;
        _possibleSquares.push_back(temp);
      }
    }
  }
}

int squareOverlap(array<int, 3> Square1, array<int, 3> Square2)
{
  int n1 = Square1.at(0);
  int m1 = Square1.at(1);
  int Size1 = Square1.at(2);
  int n2 = Square2.at(0);
  int m2 = Square2.at(1);
  int Size2 = Square2.at(2);
  if (m1 > m2 + (Size2-1) || m2 > m1 + (Size1 - 1)){
    return 0;
  }
  if (n1 + (Size1 - 1) < n2 || n2 + (Size2 - 1) < n1){
    return 0;
  }
  return 1;
}

int countOptionsRecursive(vector<array<int, 3>> auxiliarvector, array<int, 3> Square,int j){
  bool l = true;
  int i = 1;
  int k = 0;
  auxiliarvector.push_back(Square);
  for(array<int, 3> Square1: _possibleSquares){
    if(j <= k){
      j++;
      for(array<int, 3> Square2: auxiliarvector){
        if(squareOverlap(Square2,Square1) == 1){
          l = false;
          break;
        }
        else{
        }
      }
      if(l){
        i += countOptionsRecursive(auxiliarvector,Square1,j);
      }
    }
    k++;
    l = true;

  }
  auxiliarvector.pop_back();
  return i;
}

int countOptions(){
  int i = 0;
  int j = 0;
  vector<array<int, 3>> _auxiliarvector;
  _auxiliarvector.reserve(_N * _M);
  for(array<int,3> Square1: _possibleSquares){
    j++;
    i += countOptionsRecursive(_auxiliarvector,Square1,j);
  }
  if (i == 0) {
    for(int p : _path){
      if(p != 0){
        return 1;
      }
    }
    return 0;
  }
  i += 1;
  return i;
}


int main()
{
  using namespace std::chrono;
  high_resolution_clock::time_point t1 = high_resolution_clock::now();
  readGraph();
  findAllPossibleSquares();
  int i = countOptions();
  cout << i << endl;
  high_resolution_clock::time_point t2 = high_resolution_clock::now();
  duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
  std::cout << "It took me " << time_span.count() << " seconds.";
  std::cout << std::endl;
  return 0;
}