#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;

struct node {
    int ci, cj;
    int cost;
    node() {}
    node(int _ci, int _cj, int _cost) {
        ci = _ci;
        cj = _cj;
        cost = _cost;
    }
    
    bool operator < (const node &t) const {
        return cost > t.cost;
    }
};
class TimeMaze {
public:
    int minTime(vector<string> mat, int htime, int vtime) {
        int n = mat.size(), m = mat[0].size();
        
        int si, sj, ei, ej;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(mat[i][j] == 'S') {
                    si = i;
                    sj = j;
                }
                if(mat[i][j] == 'E') {
                    ei = i;
                    ej = j;
                    mat[i][j] = '0';
                }
            }
        }
        int di[] = {-1, 1, 0, 0};
        int dj[] = {0, 0, -1, 1};
        bool visited[n][m];
        memset(visited, false, sizeof visited);
        priority_queue<node> pq;
        pq.push(node(si, sj, 0));
        
        while(!pq.empty()) {
            node c = pq.top();
            pq.pop();
            visited[c.ci][c.cj] = true;
            if(c.ci == ei and c.cj == ej) {
                return c.cost;
            }
            for(int i = 0; i < 4; i++) {
                int ti = c.ci + di[i];
                int tj = c.cj + dj[i];
                if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
                    int t = -1;
                    if(i < 2) {
                        t = vtime;
                    }
                    else {
                        t = htime;
                    }
                    pq.push(node(ti, tj, c.cost + (mat[ti][tj] - '0') + t));
                    
                }
            }
        }
        return -1;
    }
};
int main()
{
     return 0;
}
/*
 
 
111#SE#222
 
S111111
9#####1
99E1111
 
 **/