Chess

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <vector>
#include <utility>
#include <cstdlib>
#include <deque>
#include <queue>
#include <iomanip>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <list>
#define mp make_pair
#define xx first
#define yy second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int N = (int)2000000;
const ld eps = 1e-16, eps1 = 1e-8, OOD = 1e200, PI = 3.14159265358979323;
const ull OO = (ull)(1e19 * 1.7);
const ll OOL = (ll)(1e18 * 8), mod = 1e9 + 7;


char ar[20][20];
int h, t, n, m, r[20][20];
pair<int, int> q[100000], x, y, tt;
string s[8] = { "uul", "uur", "ddl", "ddr", "rru", "rrd", "llu", "lld" };

pair<int, int> go(char c, pair<int, int> a)
{
    if (c == 'u') a.xx--;
    else if (c == 'd') a.xx++;
    else if (c == 'l') a.yy--;
    else a.yy++;
    return a;
}

bool check(string s, pair<int, int> a)
{
    bool b, b1;
    pair<int, int> c = a, a1 = a;
    for (int i = 0; i < 3; i++)
        a = go(s[i], a);
    for (int i = 2; i > -1; i--)
        c = go(s[i], c);
    b = (a.xx >= 0 && a.xx < n) && (a.yy >= 0 && a.yy < m);
    b1 = (c.xx >= 0 && c.xx < n) && (c.yy >= 0 && c.yy < m);
    a = c = a1;
    for (int i = 0; i < 3; i++)
    {
        a = go(s[i], a);
        b &= (ar[a.xx][a.yy] != '*');
    }
    b &= (ar[a.xx][a.yy] != '+');
    for (int i = 2; i > -1; i--)
    {
        c = go(s[i], c);
        b1 &= (ar[c.xx][c.yy] != '*');
    }
    b1 &= (ar[c.xx][c.yy] != '+');
    return (b || b1);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> ar[i][j];
            if (ar[i][j] == 's') q[0] = make_pair(i, j);
            else if (ar[i][j] == 'h') tt = mp(i, j), r[i][j] = 1000000;
            else r[i][j] = 1000000;
        }
    h = 1;
    while (t < h)
    {
        x = y = q[t];
        t++;
        for(int i = 0; i < 7; i++)
            if (check(s[i], x))
            {
                y = x;
                for (int j = 0; j < 3; j++)
                    y = go(s[i][j], y);
                if (r[y.xx][y.yy] <= r[x.xx][x.yy]) continue;
                r[y.xx][y.yy] = r[x.xx][x.yy] + 1;
                q[h++] = mp(y.xx, y.yy);
            }
    }
    if(r[tt.xx][tt.yy] != 1000000) cout << r[tt.xx][tt.yy];
    else cout << -1;
    return 0;
}