Source code for submission s734

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 = 1; i <= r; i++)
  98. for (int j = 1; 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 s714

grasshop.cpp

--- c4.s714.cteam101.grasshop.cpp.0.grasshop.cpp
+++ c4.s734.cteam101.grasshop.cpp.0.grasshop.cpp
@@ -95,6 +95,6 @@
                         break;
                 int grid[MAX][MAX];
-                for (int i = 0; i < r; i++)
-                        for (int j = 0; j < c; j++)
+                for (int i = 1; i <= r; i++)
+                        for (int j = 1; j <= c; j++)
                                 grid[i][j] = INT_MAX;
                 grid[grass.x][grass.y] = 0;