Source code for submission s619

Go to diff to previous submission

g.cpp

  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <string>
  7. #include <cstring>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <utility>
  11. #include <stack>
  12. #include <vector>
  13. #include <queue>
  14. #include <deque>
  15. #include <set>
  16. #include <map>
  17. #include <list>
  18.  
  19. #define SIZEOF(a) (sizeof(a)/sizeof(a[0]))
  20. #define FILL(a,b) fill(a,a+SIZEOF(a),b)
  21. #define FOR(a,b,c) for(int a=b;a<=c;a++)
  22. #define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++)
  23. #define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++)
  24. #define GETI(a) scanf("%d ", &a);
  25. #define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; }
  26.  
  27. using namespace std;
  28.  
  29. struct coords {
  30. int x,y;
  31. coords(int x, int y) : x(x),y(y) {}
  32. };
  33.  
  34.  
  35. int main(void)
  36. {
  37. int R,C;
  38. cin >> R >> C;
  39. int startX, startY;
  40. cin >> startX >> startY;
  41. int endX, endY;
  42. cin >> endX >> endY;
  43.  
  44. while (!feof(stdin)) {
  45.  
  46.  
  47. vector<vector<int> > visited(max(R,C)+1, vector<int>(max(R,C)+1,-1));
  48. visited[startX][startY] = 0;
  49.  
  50. queue<coords> q;
  51. q.push(coords(startX, startY));
  52.  
  53. if (startX == endX && startY == endY) {
  54. cout << 0 << endl;
  55. goto out;
  56. }
  57.  
  58. while (!q.empty()) {
  59. coords c = q.front();
  60. q.pop();
  61. // cerr << "at " << c.x << " " << c.y << endl;
  62. coords nbs[] = {
  63. coords(c.x-1, c.y-2),
  64. coords(c.x-1, c.y+2),
  65. coords(c.x+1, c.y-2),
  66. coords(c.x+1, c.y+2),
  67. coords(c.x-2, c.y-1),
  68. coords(c.x-2, c.y+1),
  69. coords(c.x+2, c.y-1),
  70. coords(c.x+2, c.y+1),
  71. };
  72. FORARR(i,nbs) {
  73. coords nb = nbs[i];
  74. // validate...
  75. if (nb.x < 1 || nb.x > R || nb.y < 1 || nb.y > C)
  76. continue; // bad
  77. if (visited[nb.x][nb.y] != -1) continue;
  78. visited[nb.x][nb.y] = visited[c.x][c.y] + 1;
  79. if (nb.x == endX && nb.y == endY) {
  80. // victory!
  81. cout << visited[nb.x][nb.y] << endl;
  82. goto out;
  83. }
  84. q.push(nb);
  85. }
  86.  
  87.  
  88. }
  89.  
  90. cout << "impossible" << endl;
  91. out:
  92. cin >> R >> C;
  93. cin >> startX >> startY;
  94. cin >> endX >> endY;
  95. }
  96.  
  97.  
  98.  
  99.  
  100. return 0;
  101. }
  102.  

Diff to submission s597

g.cpp

--- c4.s597.cteam092.grasshop.cpp.0.g.cpp
+++ c4.s619.cteam092.grasshop.cpp.0.g.cpp
@@ -44,4 +44,5 @@
         while (!feof(stdin)) {
           
+          
           vector<vector<int> > visited(max(R,C)+1, vector<int>(max(R,C)+1,-1));
           visited[startX][startY] = 0;
@@ -50,4 +51,9 @@
           q.push(coords(startX, startY));
           
+          if (startX == endX && startY == endY) {
+                cout << 0 << endl;
+                goto out;
+          }
+
           while (!q.empty()) {
                 coords c = q.front();
@@ -69,5 +75,5 @@
                     if (nb.x < 1 || nb.x > R || nb.y < 1 || nb.y > C)
                       continue; // bad
-                    if (visited[nb.x][nb.y] > 0) continue;
+                    if (visited[nb.x][nb.y] != -1) continue;
                     visited[nb.x][nb.y] = visited[c.x][c.y] + 1;
                     if (nb.x == endX && nb.y == endY) {
@@ -83,5 +89,5 @@
           
           cout << "impossible" << endl;
-out: {}   
+out:      
           cin >> R >> C;
           cin >> startX >> startY;