Source code for submission s686

Go to diff to previous submission

grasshop.cpp

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. int R; // Row count
  8. int C; // column count
  9. int Gr; // row pos grasshopper
  10. int Gc; // column pos grasshopper
  11. int Lr; // row pos delicious
  12. int Lc; // column pos delicious
  13.  
  14. class Position
  15. {
  16. public:
  17. int first;
  18. int second;
  19. int hops;
  20.  
  21. Position(int a, int b, int hops = 0)
  22. {
  23. first = a;
  24. second = b;
  25. this->hops = hops;
  26. }
  27.  
  28. bool operator==(const Position &pos)
  29. {
  30. if (this->first == pos.first && this->second == pos.second)
  31. return true;
  32.  
  33. return false;
  34. }
  35. };
  36.  
  37. queue<Position> q;
  38.  
  39. #define boardSize 200
  40. bool board[boardSize][boardSize];
  41.  
  42.  
  43. void clearBoard(int xsize, int ysize)
  44. {
  45. for (int i = 0 ; i < xsize ; ++i)
  46. for (int j = 0 ; j < ysize ; ++j)
  47. board[i][j] = false;
  48. }
  49.  
  50. bool validPos(Position pos)
  51. {
  52. if (pos.first < 0 || pos.first >= R)
  53. return false;
  54.  
  55. if (pos.second < 0 || pos.second >= C)
  56. return false;
  57.  
  58. if (board[pos.first][pos.second])
  59. return false;
  60.  
  61. board[pos.first][pos.second] = true;
  62.  
  63. return true;
  64. }
  65.  
  66.  
  67. void generateHops(Position actual)
  68. {
  69. Position p1 = Position(actual.first-1, actual.second+2, actual.hops+1);
  70. Position p2 = Position(actual.first+1, actual.second+2, actual.hops+1);
  71. Position p3 = Position(actual.first+2, actual.second+1, actual.hops+1);
  72. Position p4 = Position(actual.first+2, actual.second-1, actual.hops+1);
  73. Position p5 = Position(actual.first+1, actual.second-2, actual.hops+1);
  74. Position p6 = Position(actual.first-1, actual.second-2, actual.hops+1);
  75. Position p7 = Position(actual.first-2, actual.second-1, actual.hops+1);
  76. Position p8 = Position(actual.first-2, actual.second+1, actual.hops+1);
  77.  
  78. if (validPos(p1))
  79. q.push(p1);
  80. if (validPos(p2))
  81. q.push(p2);
  82. if (validPos(p3))
  83. q.push(p3);
  84. if (validPos(p4))
  85. q.push(p4);
  86. if (validPos(p5))
  87. q.push(p5);
  88. if (validPos(p6))
  89. q.push(p6);
  90. if (validPos(p7))
  91. q.push(p7);
  92. if (validPos(p8))
  93. q.push(p8);
  94. }
  95.  
  96. int main()
  97. {
  98.  
  99. while (true)
  100. {
  101.  
  102. cin >> R;
  103. if (cin.eof())
  104. break;
  105. cin >> C;
  106. cin >> Gr;
  107. cin >> Gc;
  108. cin >> Lr;
  109. cin >> Lc;
  110.  
  111. Gr--;Gc--;
  112. Lr--;Lc--;
  113.  
  114. Position target = Position(Lr, Lc);
  115. clearBoard(R,C);
  116. while (!q.empty())
  117. q.pop();
  118.  
  119. q.push(Position(Gr,Gc));
  120. while (!q.empty())
  121. {
  122. Position actual = q.front();
  123. q.pop();
  124. if (actual == target)
  125. {
  126. cout << actual.hops << endl;
  127. q.push(target);
  128. break;
  129. }
  130.  
  131. generateHops(actual);
  132.  
  133. }
  134. if (q.empty())
  135. cout << "impossible" << endl;
  136. }
  137.  
  138.  
  139. return 0;
  140. }

Diff to submission s662

grasshop.cpp

--- c4.s662.cteam054.grasshop.cpp.0.grasshop.cpp
+++ c4.s686.cteam054.grasshop.cpp.0.grasshop.cpp
@@ -37,5 +37,5 @@
 queue<Position> q;
       
-#define boardSize 100
+#define boardSize 200
 bool board[boardSize][boardSize];
 
@@ -50,6 +50,4 @@
 bool validPos(Position pos)
 {
-    
-  
     if (pos.first < 0 || pos.first >= R)
       return false;
@@ -61,4 +59,6 @@
       return false;
     
+    board[pos.first][pos.second] = true;
+    
     return true;
 }
@@ -121,5 +121,4 @@
     {
       Position actual = q.front();
-      board[actual.first][actual.second] = true;
       q.pop();
       if (actual == target)