fork download
copy 
  1. #include <vector>
  2. #include <math.h>
  3. #include <fstream>
  4. #include <iostream>
  5. #include <sstream>
  6. #include <string>
  7. #include <time.h>
  8. using namespace std;
  9.  
  10. #define e 2.718281828459045
  11. /****************************************
  12. LIZARD STRUCT
  13. ****************************************/
  14.  
  15. struct Lizard {
  16.     int pos;        // cell index where lizard is placed
  17.     int row;        // row in which lizard is placed
  18.     int col;        // column in which lizard is placed
  19.     int rowL;       // cell index upto which lizard can attack towards left along the row; includes tree cell
  20.     int rowH;       // cell index upto which lizard can attack towards right along the row; includes tree cell
  21.     int colL;       // cell index upto which lizard can attack towards top along the column; includes tree cell
  22.     int colH;       // cell index upto which lizard can attack towards bottom along the column; includes tree cell
  23.     int bdiagL;     // cell index upto which lizard can attack towards left top along \ diagonal; includes tree cell
  24.     int bdiagH;     // cell index upto which lizard can attack towards right bottom along \ diagonal; includes tree cell
  25.     int fdiagL;     // cell index upto which lizard can attack towards right top along / diagonal; includes tree cell
  26.     int fdiagH;     // cell index upto which lizard can attack towards left bottom along / diagonal; includes tree cell
  27. };
  28.  
  29.  
  30. /****************************************
  31. SEGMENT STRUCT
  32. ****************************************/
  33.  
  34. struct Segment {
  35.     int start;      // starting cell index of segment; does not include tree cell
  36.     int end;        // ending cell index of segment; does not include tree cell
  37.     int row;        // row of the segment
  38.  
  39.     Segment() {
  40.  
  41.     }
  42.  
  43.     Segment(int x1, int x2, int r) {
  44.         start = x1;
  45.         end = x2;
  46.         row = r;
  47.     }
  48. };
  49.  
  50.  
  51. /****************************************
  52. GARDEN CLASS
  53. ****************************************/
  54.  
  55. class Garden {
  56.  
  57. public:
  58.     int N;
  59.     int P;
  60.     long TreeCount;
  61.     int CountOfLizardsAdded;
  62.     vector<int> input;
  63.     vector<Segment> segments;
  64.     vector<Lizard> lizards;
  65.  
  66. public:
  67.     Garden(int n, int p) {
  68.         N = n;
  69.         P = p;
  70.         TreeCount = 0;
  71.         CountOfLizardsAdded = 0;
  72.     }
  73.  
  74.     bool CanLizardBeAddedHere(int cellIndex) {
  75.         if (input[cellIndex] == 2)
  76.             return false; // There's a tree here, so lizard can't be placed here.
  77.  
  78.         int cellRow = cellIndex / N;
  79.         int cellCol = cellIndex % N;
  80.         Lizard lz;
  81.         for (int i = 0; i < CountOfLizardsAdded; i++) {
  82.             lz = lizards[i];
  83.  
  84.             // If there are no trees, we can simplify checks for attacks by avoiding checking for trees, hence this if else condition.
  85.             if (TreeCount > 0) {
  86.                 /*
  87.                 // We don't need to check if the lizard is being attacked along the row because that's something we are taking care of while traversing the garden in the first place
  88.                 if (cellRow == lz.row && (lz.rowL <= cellIndex && cellIndex <= lz.rowH))
  89.                     return false; // cell shares the row with the lizard and is inside its attack zone
  90.                 */
  91.  
  92.                 if (cellCol == lz.col && (lz.colL <= cellIndex && cellIndex <= lz.colH))
  93.                     return false; // cell shares the column with the lizard and is inside its attack zone
  94.  
  95.                 if ((cellRow - lz.row == cellCol - lz.col) && (lz.bdiagL <= cellIndex && cellIndex <= lz.bdiagH))
  96.                     return false; // cell shares the \ diagonal with the lizard and is inside its attack zone
  97.  
  98.                 if ((cellRow - lz.row == lz.col - cellCol) && (lz.fdiagL <= cellIndex && cellIndex <= lz.fdiagH))
  99.                     return false; // cell shares the / diagonal with the lizard and is inside its attack zone
  100.             } else {
  101.                 /*
  102.                 // We don't need to check if the lizard is being attacked along the row because that's something we are taking care of while traversing the garden in the first place
  103.                 if (cellRow == lz.row)
  104.                     return false; // cell shares the row with the lizard
  105.                 */
  106.  
  107.                 if (cellCol == lz.col)
  108.                     return false; // cell shares the column with the lizard
  109.  
  110.                 if (cellRow - lz.row == cellCol - lz.col)
  111.                     return false; // cell shares the \ diagonal with the lizard
  112.  
  113.                 if (cellRow - lz.row == lz.col - cellCol)
  114.                     return false; // cell shares the / diagonal with the lizard
  115.             }
  116.         }
  117.         return true;
  118.     }
  119.  
  120.     void AddLizard(int cellIndex) {
  121.         Lizard lz;
  122.         lz.pos = cellIndex;
  123.         lz.row = cellIndex / N;
  124.         lz.col = cellIndex % N;
  125.         if (TreeCount > 0) // No need to calculate attack zone if there are no trees on the board, we can perform simple row, column and diagonal checks to confirm.
  126.             UpdateAttackZone(lz);
  127.  
  128.         lizards.push_back(lz);
  129.         CountOfLizardsAdded++;
  130.     }
  131.  
  132.     void UpdateAttackZone(Lizard &lz) {
  133.         int i;
  134.         int min;
  135.         int max;
  136.         if (CountOfLizardsAdded < P) { // Calculate the attack zone of the just added lizard only if the problem is not solved yet
  137.             // Traverse along the row leftwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends to its left.
  138.             i = lz.pos;
  139.             min = N * (i / N);
  140.             while (i >= min) {
  141.                 if (input[i] == 2 || i == min) {
  142.                     lz.rowL = i;
  143.                     break;
  144.                 }
  145.                 i--;
  146.             }
  147.  
  148.             // Traverse along the row rightwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends to its right.
  149.             i = lz.pos;
  150.             max = N * (i / N) + N - 1;
  151.             while (i <= max) {
  152.                 if (input[i] == 2 || i == max) {
  153.                     lz.rowH = i;
  154.                     break;
  155.                 }
  156.                 i++;
  157.             }
  158.  
  159.             // Traverse along the column upwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends above it.
  160.             i = lz.pos;
  161.             min = i % N;
  162.             while (i >= min) {
  163.                 if (input[i] == 2 || i == min) {
  164.                     lz.colL = i;
  165.                     break;
  166.                 }
  167.                 i = i - N;
  168.             }
  169.  
  170.             // Traverse along the column downwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends below it.
  171.             i = lz.pos;
  172.             max = N * (N - 1) + (i % N);
  173.             while (i <= max) {
  174.                 if (input[i] == 2 || i == max) {
  175.                     lz.colH = i;
  176.                     break;
  177.                 }
  178.                 i = i + N;
  179.             }
  180.  
  181.             // Traverse along the \ diagonal leftwards/upwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its left on \ diagonal.
  182.             i = lz.pos;
  183.             while (i / N >= 0 || i % N >= 0) {
  184.                 if (input[i] == 2 || i / N == 0 || i % N == 0) {
  185.                     lz.bdiagL = i;
  186.                     break;
  187.                 }
  188.                 i = i - N - 1;
  189.             }
  190.  
  191.             // Traverse along the \ diagonal rightwards/downwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its right on \ diagonal.
  192.             i = lz.pos;
  193.             while (i / N <= (N - 1) || i % N <= (N - 1)) {
  194.                 if (input[i] == 2 || i / N == (N - 1) || i % N == (N - 1)) {
  195.                     lz.bdiagH = i;
  196.                     break;
  197.                 }
  198.                 i = i + N + 1;
  199.             }
  200.  
  201.             // Traverse along the / diagonal rightwards/upwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its right on / diagonal.
  202.             i = lz.pos;
  203.             while (i / N >= 0 || i % N <= (N - 1)) {
  204.                 if (input[i] == 2 || i / N == 0 || i % N == (N - 1)) {
  205.                     lz.fdiagL = i;
  206.                     break;
  207.                 }
  208.                 i = i - N + 1;
  209.             }
  210.  
  211.             // Traverse along the / diagonal leftwards/downwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its left on / diagonal.
  212.             i = lz.pos;
  213.             while (i % N >= 0 || i / N <= (N - 1)) {
  214.                 if (input[i] == 2 || i % N == 0 || i / N == (N - 1)) {
  215.                     lz.fdiagH = i;
  216.                     break;
  217.                 }
  218.                 i = i + N - 1;
  219.             }
  220.         }
  221.  
  222.     }
  223.  
  224.     void RemoveLizard() {
  225.         if (CountOfLizardsAdded > 0) {
  226.             //cout << "\n Removing lizard at " << lizards[CountOfLizardsAdded - 1];
  227.             lizards.pop_back();
  228.             CountOfLizardsAdded--;
  229.  
  230.         }
  231.     }
  232.  
  233. public:
  234.     void CreateOutputFile() {
  235.         ofstream outputFile;
  236.  
  237.         outputFile.open("./output.txt", ios::trunc);
  238.         if (outputFile.is_open()) {
  239.             if (CountOfLizardsAdded == P) {
  240.                 outputFile << "OK\n";
  241.                 for (int k = 0; k < lizards.size(); k++)
  242.                     input[lizards[k].pos] = 1;
  243.  
  244.                 for (int i = 0; i < N; i++) {
  245.                     for (int j = 0; j < N; j++) {
  246.                         outputFile << input[N*i+j];
  247.                     }
  248.                     outputFile << "\n";
  249.                 }
  250.             } else {
  251.                 outputFile << "FAIL";
  252.             }
  253.             outputFile.close();
  254.         }
  255.     }
  256. };
  257.  
  258. /****************************************
  259. BFS STRATEGY
  260. ****************************************/
  261.  
  262. class BFSStrategy {
  263.  
  264. private:
  265.     vector<Garden> states;
  266.     Garden * grdn;
  267.  
  268. public:
  269.     BFSStrategy(Garden &g) {
  270.         grdn = &g;
  271.     }
  272.  
  273. public:
  274.     Garden Execute() {
  275.         int startIndex;
  276.         int depth;
  277.         for (int i = 0; i < grdn->N * grdn->N; i++) {
  278.             Garden gNew = *grdn;
  279.             if (gNew.CanLizardBeAddedHere(i)) {
  280.                 gNew.AddLizard(i);
  281.                 states.push_back(gNew);
  282.             }
  283.  
  284.             depth = 0;
  285.             while (!states.empty()) {
  286.                 Garden gResult = states.front();
  287.                 states.erase(states.begin());
  288.                 if (gResult.CountOfLizardsAdded == gResult.P) // Should we move this before placing a node in the final array? This would reduce some complexity, both for BFS and DFS.
  289.                     return gResult;
  290.  
  291.                 if (gResult.TreeCount > 0)
  292.                     startIndex = (gResult.CountOfLizardsAdded == 0) ? 0 : gResult.lizards[gResult.CountOfLizardsAdded - 1].rowH + 1;
  293.                 else
  294.                     startIndex = (gResult.CountOfLizardsAdded == 0) ? 0 : ((gResult.lizards[gResult.CountOfLizardsAdded - 1].pos / gResult.N + 1)) * gResult.N;
  295.  
  296.                 int childCount = 0;
  297.                 while (startIndex < gResult.N * gResult.N && ((depth < 5 && childCount < 4) || (depth >= 5 && childCount < 1))) {
  298.                     Garden gChild = gResult;
  299.                     if (gChild.CanLizardBeAddedHere(startIndex)) {
  300.                         gChild.AddLizard(startIndex);
  301.                         states.push_back(gChild);
  302.                         childCount++;
  303.                     }
  304.                     startIndex++;
  305.                 }
  306.                 depth++;
  307.             }
  308.         }
  309.         return Garden(1, 1);
  310.     }
  311. };
  312.  
  313. /****************************************
  314. DFS STRATEGY
  315. ****************************************/
  316.  
  317. class DFSStrategy {
  318.  
  319. private:
  320.     Garden * grdn;
  321.  
  322. public:
  323.     DFSStrategy(Garden &g) {
  324.         grdn = &g;
  325.     }
  326.  
  327. public:
  328.     // Traverse cell by cell, row by row, from top left to bottom right
  329.     bool Execute() {
  330.         if (grdn->CountOfLizardsAdded == grdn->P)
  331.             return true;
  332.  
  333.         // By starting from the appropriate cell along the row, we can avoid row safety check. This appropriate cell would either be after a tree on the same row or will be on the next row if there are no trees on the same row, as we are traversing from left to right & top to bottom.
  334.         int startIndex;
  335.         if (grdn->TreeCount > 0)
  336.             startIndex = (grdn->CountOfLizardsAdded == 0) ? 0 : grdn->lizards[grdn->CountOfLizardsAdded - 1].rowH + 1;
  337.         else
  338.             startIndex = (grdn->CountOfLizardsAdded == 0) ? 0 : ((grdn->lizards[grdn->CountOfLizardsAdded - 1].pos / grdn->N + 1)) * grdn->N;
  339.  
  340.         long totalCells = grdn->N * grdn->N;
  341.         for (int index = startIndex; index < totalCells; index++) {
  342.             if (grdn->TreeCount == 0 && (grdn->N - index / grdn->N) < (grdn->P - grdn->CountOfLizardsAdded))
  343.                 return false; // no point going down this branch further because it's not going to yield a solution because number of rows left is less than number of lizards yet to be placed.
  344.  
  345.             if (grdn->CanLizardBeAddedHere(index)) {
  346.                 grdn->AddLizard(index);
  347.                 bool hasChildren = Execute();
  348.                 if (hasChildren)
  349.                     return true;
  350.                 grdn->RemoveLizard();
  351.             }
  352.         }
  353.         return false;
  354.     }
  355.  
  356.     // Traverse segment by segment, cell by cell, from top left to bottom right
  357.     bool Execute(long startingSmgntIndex) {
  358.         if (grdn->CountOfLizardsAdded == grdn->P)
  359.             return true;
  360.  
  361.         long totalSgmntCount = grdn->segments.size();
  362.  
  363.         for (long sIndex = startingSmgntIndex; sIndex < totalSgmntCount; sIndex++) {
  364.             if (totalSgmntCount - sIndex < grdn->P - grdn->CountOfLizardsAdded)
  365.                 return false; // No point going down this branch further; it's not going to yield a solution because number of segments left is less than number of lizards yet to be placed.
  366.  
  367.             for (int cIndex = grdn->segments[sIndex].start; cIndex <= grdn->segments[sIndex].end; cIndex++) {
  368.                 if (grdn->CanLizardBeAddedHere(cIndex)) {
  369.                     grdn->AddLizard(cIndex);
  370.                     bool hasChildren = Execute(sIndex + 1);
  371.                     if (hasChildren)
  372.                         return true;
  373.                     grdn->RemoveLizard();
  374.                 }
  375.             }
  376.         }
  377.         return false;
  378.     }
  379. };
  380.  
  381. /****************************************
  382. SA STRATEGY
  383. ****************************************/
  384. class SAStrategy{
  385.  
  386. private:
  387.     Garden * grdn;
  388.  
  389. public:
  390.     SAStrategy(Garden &g) {
  391.         grdn = &g;
  392.     }
  393.  
  394. public:
  395.     void Execute() {
  396.     	double temp = 1000;
  397.         vector<Lizard> currentState;
  398.         vector<Lizard> nextState;
  399.         int cellIndex;
  400.         Segment sgmnt;
  401.  
  402.         for (int i = 0; i < grdn->P; i++) {
  403.             sgmnt = grdn->segments[i];
  404.             cellIndex = random() % (sgmnt.end - sgmnt.start + 1) + sgmnt.start;
  405.             currentState.push_back(GetLizard(cellIndex));
  406.             grdn->input[cellIndex] = 1;
  407.         }
  408.  
  409.         long totalSgmntCount = grdn->segments.size();
  410.         long sIndex;
  411.         int i;
  412.         double d = 0.0001;
  413.         time_t end = time(NULL) + 60*4.5;
  414.         while (time(NULL) <= end) {
  415.             temp = 1 / ((double)grdn->P * log(d));
  416.             d = d + 0.001;
  417.  
  418.             nextState = currentState;
  419.  
  420.             i = random() % grdn->P;
  421.             while (true) {
  422.                 sIndex = random() % totalSgmntCount;
  423.                 sgmnt = grdn->segments[sIndex];
  424.                 cellIndex = random() % (sgmnt.end - sgmnt.start + 1) + sgmnt.start;
  425.                 if (grdn->input[cellIndex] == 0)
  426.                     break;
  427.             }
  428.  
  429.             nextState[i] = GetLizard(cellIndex);
  430.  
  431.             double diff = GetNumConflicts(nextState) - GetNumConflicts(currentState);
  432.  
  433.             if (diff < 0 || (diff > 0 && pow(e, -diff/temp) > (random() % 1000)/(double)1000)) {
  434.                 grdn->input[currentState[i].pos] = 0;
  435.                 grdn->input[cellIndex] = 1;
  436.                 currentState = nextState;
  437.             }
  438.  
  439.             if (IsCurrentStateGood(currentState)) {
  440.                 grdn->CountOfLizardsAdded = currentState.size();
  441.                 grdn->lizards = currentState;
  442.                 return;
  443.             }
  444.         }
  445.         return;
  446.     }
  447.  
  448.     Lizard GetLizard(int cellIndex) {
  449.         Lizard lz;
  450.         lz.pos = cellIndex;
  451.         lz.row = cellIndex / grdn->N;
  452.         lz.col = cellIndex % grdn->N;
  453.         if (grdn->TreeCount > 0)
  454.             UpdateAttackZone(lz);
  455.         return lz;
  456.     }
  457.  
  458.     bool IsCurrentStateGood(vector<Lizard> &state) {
  459.         return GetNumConflicts(state) == 0;
  460.     }
  461.  
  462.     int GetNumConflicts(vector<Lizard> &state) {
  463.         int conflicts = 0;
  464.         Lizard lz;
  465.  
  466.         for (int li = 0; li < state.size() - 1; li++) {
  467.             int cellIndex = state[li].pos;
  468.             int cellRow = state[li].row;
  469.             int cellCol = state[li].col;
  470.  
  471.             for (int j = li + 1; j < state.size(); j++) {
  472.                    lz = state[j];
  473.  
  474.                 // If there are no trees, we can simplify checks for attacks by avoiding checking for trees, hence this if else condition.
  475.                 if (grdn->TreeCount > 0) {
  476.                     if (cellRow == lz.row && (lz.rowL <= cellIndex && cellIndex <= lz.rowH)) {
  477.                         conflicts++; // cell shares the row with the lizard and is inside its attack zone
  478.                         continue;
  479.                     }
  480.  
  481.                     if (cellCol == lz.col && (lz.colL <= cellIndex && cellIndex <= lz.colH)) {
  482.                         conflicts++; // cell shares the column with the lizard and is inside its attack zone
  483.                         continue;
  484.                     }
  485.  
  486.                     if ((cellRow - lz.row == cellCol - lz.col) && (lz.bdiagL <= cellIndex && cellIndex <= lz.bdiagH)) {
  487.                         conflicts++; // cell shares the \ diagonal with the lizard and is inside its attack zone
  488.                         continue;
  489.                     }
  490.  
  491.                     if ((cellRow - lz.row == lz.col - cellCol) && (lz.fdiagL <= cellIndex && cellIndex <= lz.fdiagH)) {
  492.                         conflicts++; // cell shares the / diagonal with the lizard and is inside its attack zone
  493.                         continue;
  494.                     }
  495.  
  496.                 } else {
  497.                     if (cellRow == lz.row) {
  498.                         conflicts++; // cell shares the row with the lizard
  499.                         continue;
  500.                     }
  501.  
  502.                     if (cellCol == lz.col) {
  503.                         conflicts++; // cell shares the column with the lizard
  504.                         continue;
  505.                     }
  506.  
  507.                     if (cellRow - lz.row == cellCol - lz.col) {
  508.                         conflicts++; // cell shares the \ diagonal with the lizard
  509.                         continue;
  510.                     }
  511.  
  512.                     if (cellRow - lz.row == lz.col - cellCol) {
  513.                         conflicts++; // cell shares the / diagonal with the lizard
  514.                         continue;
  515.                     }
  516.                 }
  517.             }
  518.         }
  519.         return conflicts;
  520.     }
  521.  
  522.     void UpdateAttackZone(Lizard &lz) {
  523.         int i;
  524.         int min;
  525.         int max;
  526.  
  527.         // Traverse along the row leftwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends to its left.
  528.         i = lz.pos;
  529.         min = grdn->N * (i / grdn->N);
  530.         while (i >= min) {
  531.             if (grdn->input[i] == 2 || i == min) {
  532.                 lz.rowL = i;
  533.                 break;
  534.             }
  535.             i--;
  536.         }
  537.  
  538.         // Traverse along the row rightwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends to its right.
  539.         i = lz.pos;
  540.         max = grdn->N * (i / grdn->N) + grdn->N - 1;
  541.         while (i <= max) {
  542.             if (grdn->input[i] == 2 || i == max) {
  543.                 lz.rowH = i;
  544.                 break;
  545.             }
  546.             i++;
  547.         }
  548.  
  549.         // Traverse along the column upwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends above it.
  550.         i = lz.pos;
  551.         min = i % grdn->N;
  552.         while (i >= min) {
  553.             if (grdn->input[i] == 2 || i == min) {
  554.                 lz.colL = i;
  555.                 break;
  556.             }
  557.             i = i - grdn->N;
  558.         }
  559.  
  560.         // Traverse along the column downwards from the lizard until a tree is found or the edge of the garden is reached; that's where lizard's attack zone ends below it.
  561.         i = lz.pos;
  562.         max = grdn->N * (grdn->N - 1) + (i % grdn->N);
  563.         while (i <= max) {
  564.             if (grdn->input[i] == 2 || i == max) {
  565.                 lz.colH = i;
  566.                 break;
  567.             }
  568.             i = i + grdn->N;
  569.         }
  570.  
  571.         // Traverse along the \ diagonal leftwards/upwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its left on \ diagonal.
  572.         i = lz.pos;
  573.         while (i / grdn->N >= 0 || i % grdn->N >= 0) {
  574.             if (grdn->input[i] == 2 || i / grdn->N == 0 || i % grdn->N == 0) {
  575.                 lz.bdiagL = i;
  576.                 break;
  577.             }
  578.             i = i - grdn->N - 1;
  579.         }
  580.  
  581.         // Traverse along the \ diagonal rightwards/downwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its right on \ diagonal.
  582.         i = lz.pos;
  583.         while (i / grdn->N <= (grdn->N - 1) || i % grdn->N <= (grdn->N - 1)) {
  584.             if (grdn->input[i] == 2 || i / grdn->N == (grdn->N - 1) || i % grdn->N == (grdn->N - 1)) {
  585.                 lz.bdiagH = i;
  586.                 break;
  587.             }
  588.             i = i + grdn->N + 1;
  589.         }
  590.  
  591.         // Traverse along the / diagonal rightwards/upwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its right on / diagonal.
  592.         i = lz.pos;
  593.         while (i / grdn->N >= 0 || i % grdn->N <= (grdn->N - 1)) {
  594.             if (grdn->input[i] == 2 || i / grdn->N == 0 || i % grdn->N == (grdn->N - 1)) {
  595.                 lz.fdiagL = i;
  596.                 break;
  597.             }
  598.             i = i - grdn->N + 1;
  599.         }
  600.  
  601.         // Traverse along the / diagonal leftwards/downwards from the lizard until a tree is found or the edge of the garden is reached, that's where lizard's attack zone ends to its left on / diagonal.
  602.         i = lz.pos;
  603.         while (i % grdn->N >= 0 || i / grdn->N <= (grdn->N - 1)) {
  604.             if (grdn->input[i] == 2 || i % grdn->N == 0 || i / grdn->N == (grdn->N - 1)) {
  605.                 lz.fdiagH = i;
  606.                 break;
  607.             }
  608.             i = i + grdn->N - 1;
  609.         }
  610.     }
  611. };
  612.  
  613.  
  614. /****************************************
  615. MAIN METHOD
  616. ****************************************/
  617.  
  618. int main() {
  619. //    clock_t start = clock();
  620. 	string algorithmInstruction;
  621.     ifstream inputFile;
  622.     ofstream outputFile;
  623.     int N;
  624.     int P;
  625.  
  626.     Garden g(0, 0);
  627.  
  628.     inputFile.open("./input.txt");
  629.     if (inputFile.is_open()) {
  630.         inputFile >> algorithmInstruction;
  631. 		inputFile >> N;
  632. 		inputFile >> P;
  633.  
  634.         g = Garden(N, P);
  635. 		char num = inputFile.get();
  636.         while (inputFile.good()) {
  637.             if (num == '2') {
  638.                 g.input.push_back(2);
  639.                 g.TreeCount++;
  640.             }
  641.  
  642.             if (num == '0')
  643.                 g.input.push_back(0);
  644.  
  645.             num = inputFile.get();
  646.         }
  647.         inputFile.close();
  648.     }
  649.  
  650.     // Create segments
  651.     int previousTreeIndex;
  652.     for (int i = 0; i < g.N * g.N; i++) {
  653.         if (i % N == 0) // We are at the beginning of the row. For the ease of visualization and calculation, let's assume there is a tree to the left of it, outside the edge of the board.
  654.             previousTreeIndex = i - 1;
  655.  
  656.         if (g.input[i] == 2) { // We have encountered a tree. If there is no tree to its immediate left, create a new segment. This will also take care of left edge because of the way we are setting previousTreeIndex above. In any case, reset previousTreeIndex to current index.
  657.             if (i - previousTreeIndex > 1)
  658.                 g.segments.push_back(Segment(previousTreeIndex + 1, i - 1, i / N));
  659.             previousTreeIndex = i;
  660.         }
  661.  
  662.         if (i % N == N - 1 && i - previousTreeIndex > 0) // We are at the end of the row. If there is no tree to its immediate left, create a new sgement.
  663.             g.segments.push_back(Segment(previousTreeIndex + 1, i, i / N));
  664.     }
  665.  
  666. //    for (int i = 0; i < g.segments.size(); i++)
  667. //        cout << "\n Segment " << i << ": " << g.segments[i].start << ", " << g.segments[i].end << ", " << g.segments[i].row;
  668.  
  669.  
  670. //        cout << algorithmInstruction;
  671.     // Call the right strategy based on algorithm instruction
  672.     if (algorithmInstruction == "BFS") {
  673.         BFSStrategy strategy = BFSStrategy(g);
  674.         Garden grdn = strategy.Execute();
  675.         grdn.CreateOutputFile();
  676.     } else if (algorithmInstruction == "DFS") {
  677.         DFSStrategy strategy = DFSStrategy(g);
  678.         strategy.Execute(0);
  679.         g.CreateOutputFile();
  680.     } else if (algorithmInstruction == "SA") {
  681.         SAStrategy strategy = SAStrategy(g);
  682.         //srandom((unsigned int)time(NULL));
  683.         strategy.Execute();
  684.         g.CreateOutputFile();
  685.     }
  686.  
  687. //    clock_t stop = clock();
  688. //    cout << "\n Time elapsed in ms: " << (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC << "\n";
  689.  
  690.     return 0;
  691. }
  692.  
Success #stdin #stdout 0s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/y42zOs
language:
C++ (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!