Source code for submission s623

grasshop.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cctype>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <algorithm>
  9. #include <deque>
  10. #include <list>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <vector>
  16.  
  17. #define FOR(I,A,B) for(int I = (A); I < (B); ++I)
  18.  
  19. #define INF (int)1e9
  20. #define EPS 1e-9
  21. #define PI 3.14159265358979
  22.  
  23. using namespace std;
  24.  
  25. typedef pair<int, int> ii;
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28.  
  29. int pole[111][111];
  30.  
  31.  
  32. int R, C, GR, GC, LR, LC;
  33.  
  34. struct Point{
  35. int r, c;
  36. };
  37.  
  38. bool solve() {
  39. if (scanf("%d%d%d%d%d%d",&R,&C,&GR,&GC,&LR,&LC)<0) return false;
  40.  
  41. --GR,--GC,--LR,--LC;
  42.  
  43. for(int i=0;i<R;++i)
  44. for(int j=0;j<C;++j){
  45. pole[i][j] = INF;
  46. }
  47.  
  48.  
  49. int dc[] = {1,2,2,1,-1,-2,-2,-1};
  50. int dr[] = {-2,-1,1,2,2,1,-1,-2};
  51.  
  52. queue<Point> fronta;
  53. fronta.push((Point){GR,GC});
  54. pole[GR][GC] = 0;
  55. while(!fronta.empty()){
  56. Point pc = fronta.front();
  57. fronta.pop();
  58.  
  59. if(pc.r == LR && pc.c==LC){
  60. printf("%d\n", pole[pc.r][pc.c]);
  61. return true;
  62. }
  63.  
  64.  
  65.  
  66. for(int d=0;d<8;++d){
  67. Point np = pc;
  68. np.r += dr[d];
  69. np.c+=dc[d];
  70. if(np.c<0 || np.r<0 ||np.c>=C || np.r>=R)
  71. continue;
  72. if(pole[np.r][np.c]!=INF)
  73. continue;
  74. pole[np.r][np.c] = pole[pc.r][pc.c]+1;
  75. fronta.push(np);
  76. }
  77. }
  78. printf("impossible\n");
  79.  
  80.  
  81. return true;
  82. }
  83.  
  84. int main() {
  85. while(solve());
  86. return 0;
  87. }