Source code for submission s570

grasshop.cpp

  1. #include<iostream>
  2.  
  3. #include<vector>
  4. #include<algorithm>
  5. #include<map>
  6. #include<set>
  7. #include<list>
  8. #include<stack>
  9. #include<queue>
  10.  
  11. #include<stdio.h>
  12. #include<stdlib.h>
  13. #include<math.h>
  14. #include<string.h>
  15.  
  16. using namespace std;
  17.  
  18. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  19.  
  20. #define PB push_back
  21. #define PII pair<int,int>
  22. #define PLL pair<ll,ll>
  23. #define MP make_pair
  24. #define fi first
  25. #define se second
  26.  
  27. #define SIZE(s) (int) (s).size()
  28.  
  29. #define INF 987654321
  30. #define ll long long
  31.  
  32. //----------------------
  33.  
  34. #define MAX 147
  35.  
  36. int X,Y;
  37. int beginY, beginX;
  38. int endX, endY;
  39.  
  40. int D[MAX][MAX];
  41.  
  42. int diry[8] = {1,2,2,1,-1,-2,-2,-1};
  43. int dirx[8] = {2,1,-1,-2,-2,-1,1,2};
  44.  
  45. bool ok(int y, int x)
  46. {
  47. return (y >= 0 && y < Y) && (x >= 0 && x < X);
  48. }
  49.  
  50. int bfs()
  51. {
  52. FOR(i,0,Y-1) FOR(j,0,X-1) D[i][j] = 0;
  53.  
  54. queue< PII > Q;
  55. Q.push(MP(beginY,beginX));
  56. while(!Q.empty())
  57. {
  58. PII front = Q.front();
  59. Q.pop();
  60. int d = D[front.fi][front.se];
  61. if (front.fi == endY && front.se == endX)
  62. return d;
  63. FOR(dir,0,7)
  64. {
  65. int y = front.fi + diry[dir];
  66. int x = front.se + dirx[dir];
  67. if (ok(y,x))
  68. {
  69. D[y][x] = d+1;
  70. Q.push(MP(y,x));
  71. }
  72. }
  73. }
  74. return -1;
  75. }
  76.  
  77. int main()
  78. {
  79. while(scanf("%d %d %d %d %d %d",&Y,&X,&beginY,&beginX,&endY,&endX) == 6)
  80. {
  81. beginX--;
  82. beginY--;
  83. endX--;
  84. endY--;
  85. int res = bfs();
  86. if (res==-1)
  87. printf("impossible\n");
  88. else printf("%d\n",res);
  89. }
  90. return 0;
  91. }
  92.  
  93.