Advertisement
savrasov

Chess

May 10th, 2017
336
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <cstring>
  5. #include <math.h>
  6. #include <cmath>
  7. #include <vector>
  8. #include <utility>
  9. #include <cstdlib>
  10. #include <deque>
  11. #include <queue>
  12. #include <iomanip>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <cmath>
  17. #include <list>
  18. #define mp make_pair
  19. #define xx first
  20. #define yy second
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25. typedef unsigned long long ull;
  26. typedef long double ld;
  27. typedef unsigned int uint;
  28. const int N = (int)2000000;
  29. const ld eps = 1e-16, eps1 = 1e-8, OOD = 1e200, PI = 3.14159265358979323;
  30. const ull OO = (ull)(1e19 * 1.7);
  31. const ll OOL = (ll)(1e18 * 8), mod = 1e9 + 7;
  32.  
  33.  
  34. char ar[20][20];
  35. int h, t, n, m, r[20][20];
  36. pair<int, int> q[100000], x, y, tt;
  37. string s[8] = { "uul", "uur", "ddl", "ddr", "rru", "rrd", "llu", "lld" };
  38.  
  39. pair<int, int> go(char c, pair<int, int> a)
  40. {
  41.     if (c == 'u') a.xx--;
  42.     else if (c == 'd') a.xx++;
  43.     else if (c == 'l') a.yy--;
  44.     else a.yy++;
  45.     return a;
  46. }
  47.  
  48. bool check(string s, pair<int, int> a)
  49. {
  50.     bool b, b1;
  51.     pair<int, int> c = a, a1 = a;
  52.     for (int i = 0; i < 3; i++)
  53.         a = go(s[i], a);
  54.     for (int i = 2; i > -1; i--)
  55.         c = go(s[i], c);
  56.     b = (a.xx >= 0 && a.xx < n) && (a.yy >= 0 && a.yy < m);
  57.     b1 = (c.xx >= 0 && c.xx < n) && (c.yy >= 0 && c.yy < m);
  58.     a = c = a1;
  59.     for (int i = 0; i < 3; i++)
  60.     {
  61.         a = go(s[i], a);
  62.         b &= (ar[a.xx][a.yy] != '*');
  63.     }
  64.     b &= (ar[a.xx][a.yy] != '+');
  65.     for (int i = 2; i > -1; i--)
  66.     {
  67.         c = go(s[i], c);
  68.         b1 &= (ar[c.xx][c.yy] != '*');
  69.     }
  70.     b1 &= (ar[c.xx][c.yy] != '+');
  71.     return (b || b1);
  72. }
  73.  
  74. int main()
  75. {
  76.     cin >> n >> m;
  77.     for (int i = 0; i < n; i++)
  78.         for (int j = 0; j < m; j++)
  79.         {
  80.             cin >> ar[i][j];
  81.             if (ar[i][j] == 's') q[0] = make_pair(i, j);
  82.             else if (ar[i][j] == 'h') tt = mp(i, j), r[i][j] = 1000000;
  83.             else r[i][j] = 1000000;
  84.         }
  85.     h = 1;
  86.     while (t < h)
  87.     {
  88.         x = y = q[t];
  89.         t++;
  90.         for(int i = 0; i < 7; i++)
  91.             if (check(s[i], x))
  92.             {
  93.                 y = x;
  94.                 for (int j = 0; j < 3; j++)
  95.                     y = go(s[i][j], y);
  96.                 if (r[y.xx][y.yy] <= r[x.xx][x.yy]) continue;
  97.                 r[y.xx][y.yy] = r[x.xx][x.yy] + 1;
  98.                 q[h++] = mp(y.xx, y.yy);
  99.             }
  100.     }
  101.     if(r[tt.xx][tt.yy] != 1000000) cout << r[tt.xx][tt.yy];
  102.     else cout << -1;
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement