Source code for submission s563

grasshop.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. const int dr[] = {-2,-1,1,2,2,1,-1,-2};
  31. const int dc[] = {1,2,2,1,-1,-2,-2,-1};
  32. const int MAX = 107;
  33. int R, C, sr, sc, er, ec;
  34. int dp[MAX][MAX];
  35. inline bool check(int r, int c) { return r >= 0 && r < R && c >= 0 && c < C; }
  36.  
  37. int main()
  38. {
  39. while (scanf("%d%d%d%d%d%d", &R, &C, &sr, &sc, &er, &ec) == 6)
  40. {
  41. --sr, --sc, --er, --ec;
  42. REP(i,R) REP(j,C) dp[i][j] = INF;
  43. queue<pair<int, int> > manage;
  44. manage.push(make_pair(sr, sc));
  45. dp[sr][sc] = 0;
  46.  
  47. while (!manage.empty() && dp[er][ec] == INF)
  48. {
  49. pair<int, int> temp = manage.front();
  50. manage.pop();
  51.  
  52. REP(d, 8)
  53. {
  54. int r = temp.first+dr[d], c = temp.second+dc[d];
  55. if (check(r, c) && dp[r][c] == INF)
  56. {
  57. dp[r][c] = dp[temp.first][temp.second]+1;
  58. manage.push(make_pair(r, c));
  59. }
  60. }
  61. }
  62.  
  63. if (dp[er][ec] == INF) printf("impossible\n");
  64. else printf("%d\n", dp[er][ec]);
  65. }
  66. return 0;
  67. }
  68.