vlatkovski

Cokoladna Kocka

Aug 28th, 2016
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. //
  9. bool ima(pair<int, int> &e, set<pair<int, int>> &s) {
  10.     return s.find(e) != s.end();
  11. }
  12.  
  13. //ovie mi trebaat ovde
  14. int n, m, iteracii = 0, kocki_zemeni;
  15.  
  16. //
  17. void zemi(set<pair<int, int>> &cokolado, vector<pair<int, int>> &to_do) {
  18.  
  19.     vector<pair<int, int>> next;
  20.  
  21.     for (unsigned int i = 0; i < to_do.size(); ++i) {
  22.         int r = to_do[i].first;
  23.         int k = to_do[i].second;
  24.  
  25.         //cout << "r:" << r << " k:" << k << endl;
  26.         pair<int, int> rm = {r - 1, k};
  27.         if (r - 1 >= 0 && !ima(rm, cokolado)) {
  28.             cokolado.insert(rm);
  29.             next.push_back(rm);
  30.         }
  31.  
  32.         pair<int, int> rp = {r + 1, k};
  33.         if (r + 1 < n && !ima(rp, cokolado)) {
  34.             cokolado.insert(rp);
  35.             next.push_back(rp);
  36.         }
  37.  
  38.         pair<int, int> km = {r, k - 1};
  39.         if (k - 1 >= 0 && !ima(km, cokolado)) {
  40.             cokolado.insert(km);
  41.             next.push_back(km);
  42.         }
  43.  
  44.         pair<int, int> kp = {r, k + 1};
  45.         if (k + 1 < m && !ima(kp, cokolado)) {
  46.             cokolado.insert(kp);
  47.             next.push_back(kp);
  48.         }
  49.     }
  50.  
  51.     if (next.size() != 0) {
  52.         iteracii++;
  53.  
  54.         kocki_zemeni = next.size();
  55.         to_do.clear();
  56.  
  57.         zemi(cokolado, next);
  58.     }
  59. }
  60.  
  61. //main
  62. int main() {
  63.     int pocetok_r, pocetok_k;
  64.     cin >> n >> m >> pocetok_r >> pocetok_k;
  65.  
  66.     pair<int, int> pocetok = {pocetok_r - 1, pocetok_k - 1};
  67.  
  68.     set<pair<int, int>> cokolado = {pocetok};
  69.     vector<pair<int, int>> pocetok_v = {pocetok};
  70.  
  71.     zemi(cokolado, pocetok_v);
  72.  
  73.     cout << iteracii << " " << kocki_zemeni << endl;
  74.  
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment