Source code for submission s636

grasshop.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. #include <queue>
  5. #include <climits>
  6. #include <cstdio>
  7.  
  8.  
  9. using namespace std;
  10.  
  11. int field[105][105];
  12. bool vis[105][105];
  13. int x[] = {1,2,2,1,-1,-2,-2,-1};
  14. int y[] = {-2,-1,1,2,2,1,-1,-2};
  15.  
  16. int r,c,gx,gy,lx,ly;
  17.  
  18. bool check(int x, int y){
  19. if(x < 1 || x >= c || y < 1 || y >= r)
  20. return false;
  21. return true;
  22. }
  23.  
  24. int main(){
  25.  
  26. while(cin >> r >> c>>gy>>gx>>ly>>lx){
  27. for(int i = 0; i < r + 1; i++)
  28. for(int j = 0; j < c + 1; j++)
  29. vis[i][j] = false;
  30.  
  31. queue < pair <int,int> > q;
  32. q.push( pair<int,int>(gx,gy) );
  33. field[gy][gx] = 0;
  34. vis[gy][gx] = true;
  35. bool ok = false;
  36.  
  37. pair<int,int> fq;
  38. while(!q.empty()){
  39. fq = q.front();
  40. q.pop();
  41.  
  42. if(fq.first == lx && fq.second == ly){
  43. ok = true;
  44. break;
  45. }
  46.  
  47. for(int i = 0; i < 8; i++){
  48. if(check(fq.first + x[i], fq.second + y[i]))
  49. if(!vis[fq.second + y[i]][fq.first + x[i]]){
  50. vis[fq.second + y[i]][fq.first + x[i]] = true;
  51. field[fq.second + y[i]][fq.first + x[i]] = field[fq.second][fq.first] + 1;
  52. q.push( pair<int,int>(fq.first + x[i],fq.second + y[i]) );
  53. }
  54. }
  55. }
  56. if(ok)
  57. cout << field[ly][lx] << endl;
  58. else
  59. cout << "impossible" << endl;
  60.  
  61. }
  62.  
  63.  
  64.  
  65. return 0;
  66. }
  67.