Miting OJI X 2016

#include <fstream>
#include <iomanip>
#include <queue>
#include <cstring>
using namespace std;
ifstream cin("miting.in");
ofstream cout("miting.out");
queue<pair<int,int>> q;
int di[] = {0,0,1,-1}, dj[] = {1,-1,0,0};
char mat[101][101], cuv[11];
int dp[11][11][61][61],visited[61][61];
const int inf = 1e9;
int cerinta, n ,m;
pair<int,int> poz[11];
int index(char c)
{
    return (strchr(cuv,c) - cuv) + 1 ;
}
int main()
{
    cin >> cerinta >> n >> m >> cuv;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin >> mat[i][j];
    if(cerinta == 1)
    {
        int xi=inf, yi=inf, xf=-inf, yf=-inf;
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++)
                if(mat[i][j]!= '#' && mat[i][j]!='_')
                {
                    xi = min(xi,i); yi = min(yi,j);
                    xf = max(xf,i); yf = max(yf,j);
                }
        cout << (xf - xi + 1) * (yf - yi + 1);
        return 0;
    }
    /// Initializam vectorul dp[][][][] cu valori mari..
    int cuvLen = strlen(cuv);
    for(int i = 1;i<=cuvLen;i++)
        for(int j = 1;j<=cuvLen;j++)
            for(int k = 1;k<=n;k++)
                for(int l = 1;l<=m;l++)
                    dp[i][j][k][l] = 1e9;
    /// Salvam pozitiile literelor in poz.
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            if(mat[i][j] != '#' && mat[i][j]!='_')
                poz[index(mat[i][j])] = {i,j};
    /// Facem un lee pornind din fiecare litera.
    for(int i = 1;i<=cuvLen;i++)
    {
        q.push(poz[i]);
        int x = poz[i].first, y = poz[i].second;
        dp[i][i][x][y] = 0;
        while(!q.empty())
        {
            x = q.front().first;
            y = q.front().second;
            for(int k = 0; k<4;k++)
            {
                int cx = x + di[k];
                int cy = y + dj[k];
                if(cx < 1 || cy < 1 || cx > n || cy > m)
                    continue;
                if(mat[cx][cy] == '#' || dp[i][i][cx][cy] <= dp[i][i][x][y]) continue;
                dp[i][i][cx][cy] = dp[i][i][x][y] + 1;
                /// Daca elementul este deja in coada nu are rost sa il pun iar.
                if(!visited[cx][cy])
                    q.push({cx,cy}),visited[cx][cy] = true;
            }
            q.pop();
            visited[x][y] = false;
        }
    }
    /// Afisarea acestor matrici :
    /*for(int i = 1;i<=cuvLen;i++,cout<<'\n')
    {
        cout << "MAT " << i << ":\n";
        for(int j = 1;j<=n;j++,cout<<'\n')
             for(int k = 1;k<=m;k++)
             {
                 if(dp[i][i][j][k] == 1e9)
                    cout <<setw(2) << -1 << ' ';
                 else cout << setw(2) << dp[i][i][j][k] << ' ';
             }
    }*/

    /// Acum completam toate celelalte pozitii din dp.
    for(int len = 2; len <= cuvLen;len++)
    {
        for(int i = 1;i <= cuvLen - len + 1; i++)
        {
            int j = i + len - 1;
            for(int p = i; p < j;p++)
                for(int L = 1; L <= n; L++)
                    for(int C = 1; C <= m; C++)
                        if(mat[L][C]!='#')
                            dp[i][j][L][C] = min(dp[i][j][L][C], dp[i][p][L][C] + dp[p+1][j][L][C]);
            /// Afisarea matricilor fara a lua in calcul unirea dintre doua litere :
            /*cout << "Matrice inainte de Lee\n";
            cout << "len = " << len << ',' << " i = " << i << " ,j = " << j << '\n' << '\n';
            for(int L = 1; L <= n; L++,cout << '\n')
                for(int C = 1; C<=m; C++)
                {
                    if(dp[i][i][L][C] == 1e9)
                        cout <<setw(2) << -1 << ' ';
                    else cout << setw(2) << dp[i][j][L][C] << ' ';
                }
            cout << '\n';*/

            /// Acum efectuam Lee-ul pentru a lua in calcul unirea dintre doua litere.
            for(int L = 1; L <= n; L++)
                for(int C = 1; C <= m; C++)
                {
                    if(mat[L][C] == '#')
                        continue;
                    q.push({L,C});
                    while(!q.empty())
                    {
                        int x = q.front().first;
                        int y = q.front().second;
                        for(int k = 0; k<4; k++)
                        {
                            int cx = x + di[k];
                            int cy = y + dj[k];
                            if(cx < 1 || cy < 1 || cx > n || cy > m)
                                continue;
                            if(mat[cx][cy] == '#' || dp[i][j][cx][cy] <= dp[i][j][x][y] + 1)
                                continue;
                            dp[i][j][cx][cy] = dp[i][j][x][y] + 1;
                            if(!visited[cx][cy])
                                q.push({cx,cy}),visited[cx][cy] = true;
                        }
                        q.pop();
                        visited[x][y] = false;
                    }
                }
            /// Afisarile noilor matrici
            /*cout << "Matrice dupa lee \n" << "len = " << len << ',' << " i = " << i << " ,j = " << j << '\n' << '\n';
            for(int L = 1; L <= n; L++,cout << '\n')
                for(int C = 1; C<=m; C++)
                {
                    if(dp[i][i][L][C] == 1e9)
                        cout <<setw(2) << -1 << ' ';
                    else cout << setw(2) << dp[i][j][L][C] << ' ';
                }
            cout << '\n';*/

        }
    }
    /// Afisam raspunsul.
    int sol = 1e9;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            sol = min(sol,dp[1][cuvLen][i][j]);
    cout << sol << '\n';

    return 0;
}