Source code for submission s947

Go to diff to previous submission

grasshop.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5.  
  6.  
  7. int fronta[1000000][3];
  8. int pole[1001][1001];
  9. int a,b,c,d,e,f;
  10.  
  11.  
  12. int main()
  13. {
  14. while(scanf("%i %i %i %i %i %i",&a,&b,&c,&d,&e,&f)==6)
  15. {
  16. for (int i = 1; i <= a; i++)
  17. for (int o = 1; o <= b; o++)
  18. {
  19. pole[i][o] = 0;
  20. }
  21.  
  22. int fs = 0;
  23. int fl = 0;
  24.  
  25. fronta[fs+fl][0] = c;
  26. fronta[fs+fl][1] = d;
  27. fronta[fs+fl][2] = 0;
  28. fl++;
  29.  
  30. bool ok = false;
  31.  
  32. while (fl > 0)
  33. {
  34. int x = fronta[fs][0];
  35. int y = fronta[fs][1];
  36. int n = fronta[fs][2];
  37. fs++;
  38. fl--;
  39.  
  40. if (x < 1 || x > a || y < 1 || y > b)
  41. continue;
  42.  
  43. if (pole[x][y] == 1)
  44. continue;
  45.  
  46. //printf("%i %i\n", x,y);
  47.  
  48. pole[x][y] = 1;
  49.  
  50. if (x==e && y == f)
  51. {
  52. printf("%i\n", n);
  53. ok =true;
  54. break;
  55. }
  56.  
  57. fronta[fs+fl][0] = x + 2;
  58. fronta[fs+fl][1] = y + 1;
  59. fronta[fs+fl][2] = n + 1;
  60. fl++;
  61.  
  62. fronta[fs+fl][0] = x + 1;
  63. fronta[fs+fl][1] = y + 2;
  64. fronta[fs+fl][2] = n + 1;
  65. fl++;
  66.  
  67. fronta[fs+fl][0] = x - 2;
  68. fronta[fs+fl][1] = y - 1;
  69. fronta[fs+fl][2] = n + 1;
  70. fl++;
  71.  
  72. fronta[fs+fl][0] = x - 1;
  73. fronta[fs+fl][1] = y - 2;
  74. fronta[fs+fl][2] = n + 1;
  75. fl++;
  76.  
  77. fronta[fs+fl][0] = x - 2;
  78. fronta[fs+fl][1] = y + 1;
  79. fronta[fs+fl][2] = n + 1;
  80. fl++;
  81.  
  82. fronta[fs+fl][0] = x - 1;
  83. fronta[fs+fl][1] = y + 2;
  84. fronta[fs+fl][2] = n + 1;
  85. fl++;
  86.  
  87. fronta[fs+fl][0] = x + 2;
  88. fronta[fs+fl][1] = y - 1;
  89. fronta[fs+fl][2] = n + 1;
  90. fl++;
  91.  
  92. fronta[fs+fl][0] = x + 1;
  93. fronta[fs+fl][1] = y - 2;
  94. fronta[fs+fl][2] = n + 1;
  95. fl++;
  96.  
  97. }
  98.  
  99. if (ok == false)
  100. {
  101. printf("impossible\n");
  102. }
  103.  
  104. }
  105.  
  106.  
  107. return 0;
  108. }

Diff to submission s843

grasshop.cpp

--- c4.s843.cteam114.grasshop.cpp.0.grasshop.cpp
+++ c4.s947.cteam114.grasshop.cpp.0.grasshop.cpp
@@ -3,11 +3,9 @@
 #include <math.h>
 
-int pole[200][200];
-int a,b,c,d,e,f;
 
-int cesta(int zx, int zy)
-{
-                
-}
+
+int fronta[1000000][3];
+int pole[1001][1001];
+int a,b,c,d,e,f;
 
 
@@ -16,9 +14,95 @@
         while(scanf("%i %i %i %i %i %i",&a,&b,&c,&d,&e,&f)==6)
         {
-                int dx = abs(c-e);
-                int dy = abs(f-d);
+                for (int i = 1; i <= a; i++)
+                        for (int o = 1; o <= b; o++)
+                        {
+                                pole[i][o] = 0;
+                        }
+        
+        int fs = 0;
+        int fl = 0;
+
+        fronta[fs+fl][0] = c;
+        fronta[fs+fl][1] = d;
+        fronta[fs+fl][2] = 0;
+        fl++;
+
+        bool ok = false;
+
+        while (fl > 0)
+        {
+                int x = fronta[fs][0];
+                int y = fronta[fs][1];
+                int n = fronta[fs][2];
+                fs++;
+                fl--;
                 
-                                
+                if (x < 1 || x > a || y < 1 || y > b)
+                        continue;
+
+                if (pole[x][y] == 1)
+                        continue;
+
+                //printf("%i %i\n", x,y);
+
+                pole[x][y] = 1;
+
+                if (x==e && y == f)
+                {
+                        printf("%i\n", n);
+                        ok =true;
+                        break;
+                }
+
+                fronta[fs+fl][0] = x + 2;
+                fronta[fs+fl][1] = y + 1;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+
+                fronta[fs+fl][0] = x + 1;
+                fronta[fs+fl][1] = y + 2;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+                
+                fronta[fs+fl][0] = x - 2;
+                fronta[fs+fl][1] = y - 1;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+                
+                fronta[fs+fl][0] = x - 1;
+                fronta[fs+fl][1] = y - 2;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+
+                fronta[fs+fl][0] = x - 2;
+                fronta[fs+fl][1] = y + 1;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+                
+                fronta[fs+fl][0] = x - 1;
+                fronta[fs+fl][1] = y + 2;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+
+                fronta[fs+fl][0] = x + 2;
+                fronta[fs+fl][1] = y - 1;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+                
+                fronta[fs+fl][0] = x + 1;
+                fronta[fs+fl][1] = y - 2;
+                fronta[fs+fl][2] = n + 1;
+                fl++;
+
+        }
+
+        if (ok == false)
+        {
+                printf("impossible\n");
+        }
+                        
         }       
+
+
         return 0;
 }
\ No newline at end of file