b9ff079b.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 50 + 5;
const int M = 10000 + 5;

int n, m;

char mp[N][N], S[M];
pii L[N][N], R[N][N], U[N][N], D[N][N];

struct Status
{
    int x, y, dep, cost;

    inline Status(const int &x, const int &y, const int &dep, const int &cost)
    {
        this->x = x;
        this->y = y;
        this->dep = dep;
        this->cost = cost;
    }
};

int vis[N][N];

int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", mp[i] + 1);
    }
    scanf("%s", S + 1);
    int lenS = strlen(S + 1);
    S[++lenS] = '*';

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (mp[i][j] == mp[i][j - 1])
            {
                L[i][j] = L[i][j - 1];
            }
            else
            {
                L[i][j] = (pii){i, j - 1};
            }
            if (mp[i][j] == mp[i - 1][j])
            {
                U[i][j] = U[i - 1][j];
            }
            else
            {
                U[i][j] = (pii){i - 1, j};
            }
        }
    }

    for (int i = n; i >= 1; --i)
    {
        for (int j = m; j >= 1; --j)
        {
            if (mp[i][j] == mp[i][j + 1])
            {
                R[i][j] = R[i][j + 1];
            }
            else
            {
                R[i][j] = (pii){i, j + 1};
            }
            if (mp[i][j] == mp[i + 1][j])
            {
                D[i][j] = D[i + 1][j];
            }
            else
            {
                D[i][j] = (pii){i + 1, j};
            }
        }
    }

    memset(vis, -1, sizeof(vis));

    queue<Status> q;
    q.emplace(1, 1, 0, 0);

    auto transfer = [&](const Status &cur, const pii(&leap)[55][55]) {
        const int &nx = leap[cur.x][cur.y].first,
                  &ny = leap[cur.x][cur.y].second;
        if ((nx < 1 || nx > n) ||
            (ny < 1 || ny > m))
        {
            return;
        }
        if (vis[nx][ny] < cur.dep)
        {
            vis[nx][ny] = cur.dep;
            q.emplace(nx, ny, cur.dep, cur.cost + 1);
        }
    };

    while (!q.empty())
    {
        Status cur = q.front();
        q.pop();

        if (cur.dep == lenS)
        {
            printf("%d\n", cur.cost);
            return 0;
        }

        if (mp[cur.x][cur.y] == S[cur.dep + 1] && vis[cur.x][cur.y] < cur.dep + 1)
        {
            vis[cur.x][cur.y] = cur.dep + 1;
            q.emplace(cur.x, cur.y, cur.dep + 1, cur.cost + 1);
        }

        transfer(cur, L);
        transfer(cur, R);
        transfer(cur, U);
        transfer(cur, D);
    }

    return 0;
}