Source code for submission s698

Go to diff to previous submission

grasshop.cpp

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <list>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. int gR, gC, r, c, lR, lC;
  10.  
  11.  
  12. struct State {
  13. int r, c;
  14. int steps;
  15. };
  16.  
  17. int arrR[]= {-2, -1, 1, 2, 2, 1, -1, -2};
  18. int arrC[] = {1, 2, 2, 1, -1, -2, -2, -1};
  19.  
  20. int solve ( bool ** chessBoard){
  21.  
  22. list <State> l;
  23. State s;
  24. s.r = gR;
  25. s.c = gC;
  26. s.steps = 0;
  27. l.push_back(s);
  28.  
  29. while (!l.empty()){
  30. State t = *(l.begin());
  31. l.pop_front();
  32.  
  33. for (int i = 0; i < 8 ; i++){
  34. int tR = t.r + arrR[i];
  35. int tC = t.c + arrC[i];
  36.  
  37. if (tR <= 0 || tR > r || tC <= 0 || tC > c){
  38. continue;
  39. }
  40. if (chessBoard[tR][tC]) continue;
  41. chessBoard[tR][tC] = true;
  42. State tmp;
  43. tmp.r = tR;
  44. tmp.c = tC;
  45. tmp.steps = t.steps + 1;
  46. l.push_back(tmp);
  47. if (tmp.r == lR && tmp.c == lC){
  48. return tmp.steps;
  49. }
  50. }
  51. }
  52. return -1;
  53. }
  54.  
  55.  
  56. int main(){
  57.  
  58. bool ** chessBoard;
  59.  
  60.  
  61. while ( cin >> r >> c >> gR >> gC >> lR >> lC){
  62. if (gR == lR && gC == lC) {
  63. cout << 0 << endl;
  64. continue;
  65. }
  66.  
  67. chessBoard = new bool * [r + 1];
  68. for (int i = 0; i <= r ; i++){
  69. chessBoard[i] = new bool[c + 1];
  70. for (int j = 0; j <= c; j++){
  71. chessBoard[i][j] = false;
  72. }
  73. }
  74. chessBoard[gR][gC] = true;
  75. int result = solve(chessBoard);
  76.  
  77. if (result < 0){
  78. cout << "impossilble" << endl;
  79. } else {
  80. cout << result << endl;
  81. }
  82.  
  83. for (int i = 0; i <= r ; i++){
  84. delete [] chessBoard[i];
  85. }
  86. // delete [] chessBoard;
  87. }
  88.  
  89. return 0;
  90. }
  91.  

Diff to submission s692

grasshop.cpp

--- c4.s692.cteam013.grasshop.cpp.0.grasshop.cpp
+++ c4.s698.cteam013.grasshop.cpp.0.grasshop.cpp
@@ -65,7 +65,7 @@
                 }
         
-                chessBoard = new bool * [r];
+                chessBoard = new bool * [r + 1];
                 for (int i = 0; i <= r ; i++){
-                        chessBoard[i] = new bool[c];
+                        chessBoard[i] = new bool[c + 1];
                         for (int j = 0; j <= c; j++){
                                 chessBoard[i][j] = false;