Source code for submission s714

Go to diff to previous submission

grasshop.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <climits>
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9.  
  10. #include <vector>
  11. #include <string>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <stack>
  16. #include <set>
  17.  
  18. using namespace std;
  19.  
  20. typedef unsigned int uint;
  21. typedef long double num;
  22. typedef long long int lint;
  23. typedef struct { int x, y; } intpoint;
  24. typedef struct { num x, y; } numpoint;
  25. typedef struct { lint x, y; } lintpoint;
  26.  
  27. typedef struct
  28. {
  29. 	int x, y;
  30. } point;
  31.  
  32. #define EPS (1e-7L)
  33. #define PI (4.0L * atanl(1.0L))
  34. #define MAX 101
  35.  
  36. #define min(a, b) ((a) < (b) ? (a) : (b))
  37. #define max(a, b) ((a) > (b) ? (a) : (b))
  38. #define abs(a) ((a) < 0 ? -(a) : (a))
  39.  
  40. vector<point> directions;
  41. int r, c;
  42.  
  43. bool inrange(point test)
  44. {
  45. 	return test.x >= 1 && test.x <= r && test.y >= 1 && test.y <= c;
  46. }
  47.  
  48. int solve(int grid[MAX][MAX], point g, point l)
  49. {
  50. 	queue<point> q;
  51. 	q.push(g);
  52.  
  53. 	while(!q.empty())
  54. 	{
  55. 		point aux = q.front();
  56. 		q.pop();
  57.  
  58. 		if (aux.x == l.x && aux.y == l.y)
  59. 			return grid[aux.x][aux.y];
  60.  
  61. 		for (uint i = 0; i < directions.size(); i++)
  62. 		{
  63. 			point temp = aux;
  64. 			temp.x += directions[i].x;
  65. 			temp.y += directions[i].y;
  66. 			if (inrange(temp))
  67. 				if (grid[temp.x][temp.y] > grid[aux.x][aux.y] + 1)
  68. 				{
  69. 					grid[temp.x][temp.y] = grid[aux.x][aux.y] + 1;
  70. 					q.push(temp);
  71. 				}
  72. 		}
  73. 	}
  74.  
  75. 	return -1;
  76. }
  77.  
  78.  
  79. int main(int argc, char *argv[]) {
  80.  
  81. 	directions.push_back((point){  2, -1});
  82. 	directions.push_back((point){  2,  1});
  83. 	directions.push_back((point){  1,  2});
  84. 	directions.push_back((point){  1, -2});
  85. 	directions.push_back((point){ -1, -2});
  86. 	directions.push_back((point){ -1,  2});
  87. 	directions.push_back((point){ -2, -1});
  88. 	directions.push_back((point){ -2,  1});
  89.  
  90.  
  91. 	point grass, leaf;
  92.  
  93. 	while (true) {
  94. 		if (scanf("%d %d %d %d %d %d", &r, &c, &grass.x, &grass.y, &leaf.x, &leaf.y) != 6)
  95. 			break;
  96. 		int grid[MAX][MAX];
  97. 		for (int i = 0; i < r; i++)
  98. 			for (int j = 0; j < c; j++)
  99. 				grid[i][j] = INT_MAX;
  100. 		grid[grass.x][grass.y] = 0;
  101.  
  102. 		int shortestpath = solve(grid, grass, leaf);
  103. 		if (shortestpath == -1)
  104. 			printf("impossible\n");
  105. 		else
  106. 			printf("%d\n", shortestpath);
  107.  
  108.  
  109. 	}
  110.  
  111. 	return 0;
  112. }
  113.  

Diff to submission s706

grasshop.cpp

--- c4.s706.cteam101.grasshop.cpp.0.grasshop.cpp
+++ c4.s714.cteam101.grasshop.cpp.0.grasshop.cpp
@@ -43,5 +43,5 @@
 bool inrange(point test)
 {
-        return test.x >= 1 && test.x < r && test.y >= 1 && test.y < c;
+        return test.x >= 1 && test.x <= r && test.y >= 1 && test.y <= c;
 }