Source code for submission s677

sablona.cc

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <sstream>
  12.  
  13. #include <stdio.h>
  14. #include <ctype.h>
  15. #include <math.h>
  16. #include <string.h>
  17. #include <stdlib.h>
  18.  
  19. using namespace std;
  20.  
  21. #define X first
  22. #define Y second
  23. #define MP make_pair
  24. #define PB push_back
  25. #define SZ size
  26.  
  27. int main(void)
  28. {
  29. int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k;
  30. int vrcholy[110][110];
  31. int uz[110][110];
  32. while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
  33. for (i = 1; i <= a; i++) {
  34. for (ii = 1; ii <= b; ii++) {
  35. vrcholy[i][ii] = 9999999;
  36. uz[i][ii] = -1;
  37. }
  38. }
  39. vrcholy[c][d] = 0;
  40. uz[c][d] = 1;
  41. akt = c;
  42. akt2 = d;
  43. if (akt - 1 > 0 && akt2 - 2 > 0)
  44. if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2])
  45. vrcholy[akt-1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  46. if (akt - 2 > 0 && akt2 - 1 > 0)
  47. if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2])
  48. vrcholy[akt-2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  49. if (akt + 1 <= a && akt2 - 2 > 0)
  50. if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2])
  51. vrcholy[akt+1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  52. if (akt + 2 <= a && akt2 - 1 > 0)
  53. if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2])
  54. vrcholy[akt+2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  55. if (akt - 1 > 0 && akt2 +2 <= b)
  56. if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2])
  57. vrcholy[akt-1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  58. if (akt - 2 > 0 && akt2 +1 <= b)
  59. if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2])
  60. vrcholy[akt-2][akt2 +1] = vrcholy[akt][akt2] + 1;
  61. if (akt + 1 <= a && akt2 + 2 <= b)
  62. if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
  63. vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  64. if (akt + 1 <= a && akt2 + 2 <= b)
  65. if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
  66. vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  67. for (i = 1; i <= a; i++) {
  68. for (ii = 1; ii <= b; ii++) {
  69. akt = -1;
  70. akt2 = -1;
  71. for (j = 1; j <= a; j++) {
  72. for (k = 1; k <= b; k++) {
  73. if (uz[j][k] == -1 && (akt == -1 || vrcholy[j][k] < vrcholy[akt][akt2]) && vrcholy[j][k] != 9999999) {
  74. akt = j;
  75. akt2 = k;
  76. }
  77. }
  78. }
  79. if (akt != -1) {
  80. uz[akt][akt2] = 1;
  81. if (akt - 1 > 0 && akt2 - 2 > 0)
  82. if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2])
  83. vrcholy[akt-1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  84. if (akt - 2 > 0 && akt2 - 1 > 0)
  85. if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2])
  86. vrcholy[akt-2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  87. if (akt + 1 <= a && akt2 - 2 > 0)
  88. if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2])
  89. vrcholy[akt+1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  90. if (akt + 2 <= a && akt2 - 1 > 0)
  91. if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2])
  92. vrcholy[akt+2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  93. if (akt - 1 > 0 && akt2 +2 <= b)
  94. if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2])
  95. vrcholy[akt-1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  96. if (akt - 2 > 0 && akt2 +1 <= b)
  97. if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2])
  98. vrcholy[akt-2][akt2 +1] = vrcholy[akt][akt2] + 1;
  99. if (akt + 1 <= a && akt2 + 2 <= b)
  100. if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
  101. vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  102. if (akt + 1 <= a && akt2 + 2 <= b)
  103. if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2])
  104. vrcholy[akt+1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  105. }
  106. }
  107. }
  108. if (vrcholy[e][f] != 9999999)
  109. printf("%d\n", vrcholy[e][f]);
  110. else
  111. printf("impossible\n");
  112. }
  113.  
  114.  
  115. return 0;
  116. }
  117.