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;