fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int k(string& s)
  5. {
  6.     int ks = 0;
  7.     int pos = s.find('G');
  8.     for(int p = pos; p >= 0 && s[p] != 'D'; --p)
  9.         if (s[p] == 'K') { s[p] = ' '; ++ks; }
  10.     for(int p = pos; p < s.size() && s[p] != 'D'; ++p)
  11.         if (s[p] == 'K') { s[p] = ' '; ++ks; }
  12.     return ks;
  13. }
  14.  
  15.  
  16. bool l(const string& s, int keys);
  17. bool r(const string& s, int keys);
  18.  
  19. bool l(const string& s, int keys)
  20. {
  21.     int pos = s.find('G');
  22.     if (pos == 0 || pos == s.size()-1) return true;
  23.     string t = s;
  24.     keys += k(t);
  25.     int p = pos-1;
  26.     for(; p >= 0; --p)
  27.     {
  28.         if (t[p] == 'D')
  29.         {
  30.             if (keys > 0)
  31.             {
  32.                 t[p] = ' ';
  33.                 keys--;
  34.                 t[p] = 'G';
  35.                 t[pos] = ' ';
  36.                 return l(t,keys)||r(t,keys);
  37.             }
  38.             return false;
  39.         }
  40.     }
  41.     return true;
  42. }
  43.  
  44. bool r(const string& s, int keys)
  45. {
  46.     int pos = s.find('G');
  47.     if (pos == 0 || pos == s.size()-1) return true;
  48.     string t = s;
  49.     keys += k(t);
  50.     int p = pos+1;
  51.     for(; p < t.size(); ++p)
  52.     {
  53.         if (t[p] == 'D')
  54.         {
  55.             if (keys > 0)
  56.             {
  57.                 t[p] = ' ';
  58.                 keys--;
  59.                 t[p] = 'G';
  60.                 t[pos] = ' ';
  61.                 return l(t,keys)||r(t,keys);
  62.             }
  63.             return false;
  64.         }
  65.     }
  66.     return true;
  67. }
  68.  
  69. int main(int argc, char * argv[])
  70. {
  71.  
  72.     string s = "DKDDGKKDDKDD";
  73.     cout << (l(s,0)||r(s,0)) << endl;
  74.     s = "DDKGDDKKKKKKD";
  75.     cout << (l(s,0)||r(s,0)) << endl;
  76.     s = "DDDDKKKDDKGDKKDDD";
  77.     cout << (l(s,0)||r(s,0)) << endl;
  78.  
  79. }
  80.  
Success #stdin #stdout 0s 5700KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
0
1
https://ideone.com/p1RTQK
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!