Source code for submission s618

Go to diff to previous submission

grasshop.cpp

  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstring>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. struct Point {
  9. 	int a;
  10. 	int b;
  11. };
  12.  
  13. queue <Point> trace;
  14. int grid[200][200];
  15. int a, b, a1, b1, a2, b2;
  16.  
  17. bool push (Point next) {
  18. 	Point cur = trace.front();
  19. 	if (next.a >= 0 && next.a < a && next.b >= 0 && next.b < b) {
  20. 		if (grid[cur.a][cur.b] + 1 < grid[next.a][next.b]) { 
  21. 			trace.push (next);
  22. 			grid[next.a][next.b] = grid[cur.a][cur.b] + 1;
  23. 			if (next.a == a2 && next.b == b2)
  24. 				return true;
  25. 		}
  26. 	}
  27. 	return false;
  28. }
  29.  
  30. int main() {
  31. 	while (scanf ("%d%d%d%d%d%d", &a, &b, &a1, &b1, &a2, &b2) == 6) {
  32. 		for (int i = 0; i < 200; i++)
  33. 			for (int j = 0; j < 200; j++)
  34. 				grid[i][j] = 1000000000;
  35.  
  36. 		a1--; b1--; a2--; b2--;
  37. 		Point start;
  38. 		start.a = a1;
  39. 		start.b = b1;
  40. 		grid[a1][b1] = 0;
  41. 		trace.push (start);
  42. 		while (!trace.empty()) {
  43. 			Point cur = trace.front();
  44. 			Point next;
  45. 			next.a = cur.a - 2;
  46. 			next.b = cur.b - 1;
  47. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  48. 			next.a = cur.a - 2;
  49. 			next.b = cur.b + 1;
  50. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  51. 			next.a = cur.a + 2;
  52. 			next.b = cur.b - 1;
  53. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  54. 			next.a = cur.a + 2;
  55. 			next.b = cur.b + 1;
  56. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  57. 			next.a = cur.a - 1;
  58. 			next.b = cur.b - 2;
  59. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  60. 			next.a = cur.a - 1;
  61. 			next.b = cur.b + 2;
  62. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  63. 			next.a = cur.a + 1;
  64. 			next.b = cur.b - 2;
  65. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  66. 			next.a = cur.a + 1;
  67. 			next.b = cur.b + 2;
  68. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  69. 			trace.pop();
  70. 		}
  71. 		printf ("impossible\n");	
  72. 		next:;
  73. 		while (!trace.empty()) trace.pop();
  74. 	}
  75. 	return 0;
  76. }

Diff to submission s611

grasshop.cpp

--- c4.s611.cteam010.grasshop.cpp.0.grasshop.cpp
+++ c4.s618.cteam010.grasshop.cpp.0.grasshop.cpp
@@ -34,4 +34,5 @@
                                 grid[i][j] = 1000000000;
                 
+                a1--; b1--; a2--; b2--;
                 Point start;
                 start.a = a1;