Source code for submission s625

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. 		if (a1 == a2 && b1 == b2) { printf ("0\n"); goto next; }
  37. 		a1--; b1--; a2--; b2--;
  38. 		Point start;
  39. 		start.a = a1;
  40. 		start.b = b1;
  41. 		grid[a1][b1] = 0;
  42. 		trace.push (start);
  43. 		while (!trace.empty()) {
  44. 			Point cur = trace.front();
  45. 			Point next;
  46. 			next.a = cur.a - 2;
  47. 			next.b = cur.b - 1;
  48. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  49. 			next.a = cur.a - 2;
  50. 			next.b = cur.b + 1;
  51. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  52. 			next.a = cur.a + 2;
  53. 			next.b = cur.b - 1;
  54. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  55. 			next.a = cur.a + 2;
  56. 			next.b = cur.b + 1;
  57. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  58. 			next.a = cur.a - 1;
  59. 			next.b = cur.b - 2;
  60. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  61. 			next.a = cur.a - 1;
  62. 			next.b = cur.b + 2;
  63. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  64. 			next.a = cur.a + 1;
  65. 			next.b = cur.b - 2;
  66. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  67. 			next.a = cur.a + 1;
  68. 			next.b = cur.b + 2;
  69. 			if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; }
  70. 			trace.pop();
  71. 		}
  72. 		printf ("impossible\n");	
  73. 		next:;
  74. 		while (!trace.empty()) trace.pop();
  75. 	}
  76. 	return 0;
  77. }

Diff to submission s618

grasshop.cpp

--- c4.s618.cteam010.grasshop.cpp.0.grasshop.cpp
+++ c4.s625.cteam010.grasshop.cpp.0.grasshop.cpp
@@ -34,4 +34,5 @@
                                 grid[i][j] = 1000000000;
                 
+                if (a1 == a2 && b1 == b2) { printf ("0\n"); goto next; }
                 a1--; b1--; a2--; b2--;
                 Point start;