#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long Int;

struct grph
{
    Int ver,cost;
};

vector<grph> Graph[250001];
Int magictable[501][501];
Int n,m,a,b;
Int rx,ry;

///Djikstra
Int D[250001];
bool TFO[250001];
grph Heap[1000001];
Int whereis[1000001];

Int TwoToOne(Int x,Int y)
{
    Int num=(x-1)*m + y;
    return num;
}

void OneToTwo(Int num)
{
    ry=num%m;

    if (ry==0)
    ry=m;

    rx=(num-ry)/m + 1;

    return;
}

void Update(Int hind)
{
    Int dad,son=hind;
    grph d;
    Int in;
    dad=son/2;

    while(dad>0)
    {
        if (Heap[dad].cost>Heap[son].cost)
        {
            whereis[ Heap[dad].ver ]=son;
            whereis[ Heap[son].ver ]=dad;

            d=Heap[dad];
            Heap[dad]=Heap[son];
            Heap[son]=d;

            son=dad;
        }
        else
        {
            break;
        }

        dad=son/2;
    }

    return;
}

grph RemoveTop()
{
    grph toreturn=Heap[1];
    Int dad=1,son1,son2;
    grph d;

    Heap[1].cost=999999999999;

    while(dad<500000)
    {
        son1=dad*2;
        son2=dad*2+1;

        if (Heap[son1].cost<Heap[son2].cost)
        {
            whereis[ Heap[dad].ver ]=son1;
            whereis[ Heap[son1].ver ]=dad;

            d=Heap[dad];
            Heap[dad]=Heap[son1];
            Heap[son1]=d;

            dad=son1;
        }
        else
        {
            whereis[ Heap[dad].ver ]=son2;
            whereis[ Heap[son2].ver ]=dad;

            d=Heap[dad];
            Heap[dad]=Heap[son2];
            Heap[son2]=d;

            dad=son2;
        }
    }

    return toreturn;
}

Int Djikstra(Int s,Int e)
{
    Int i,j,in;
    grph top;

    for (i=0;i<=250000;i++)
    {
        D[i]=-1;
        TFO[i]=false;
    }
    for (i=0;i<=1000000;i++)
    {
        Heap[i].ver=i;
        Heap[i].cost=999999999999;
        whereis[i]=i;
    }

    D[s]=0;
    Heap[ whereis[s] ].cost=0;
    Update(whereis[s]);

    for (i=1;i<=n*m;i++)
    {
        top=RemoveTop();

        TFO[top.ver]=true;

        if (top.ver==e)
        {
            return top.cost;
        }

        for (j=0;j<Graph[top.ver].size();j++)
        {
            if (TFO[ Graph[top.ver][j].ver ])
            {
                continue;
            }

            if ( Graph[top.ver][j].cost+top.cost < D[ Graph[top.ver][j].ver ] || D[ Graph[top.ver][j].ver ]==-1 )
            {
                D[ Graph[top.ver][j].ver ]=Graph[top.ver][j].cost+top.cost;
                Heap[ whereis[ Graph[top.ver][j].ver ] ].cost=Graph[top.ver][j].cost+top.cost;
                Update( whereis[ Graph[top.ver][j].ver ] );
            }
        }
    }

    return -1;
}

int main()
{
    freopen("exam.in","r",stdin);
    freopen("exam.out","w",stdout);

    Int i,j;
    Int curver;
    Int nextx,nexty,nextver;
    grph help;
    Int s,e;
    Int sx,sy,ex,ey;
    char ch;

    scanf("%I64d %I64d %I64d %I64d",&n,&m,&a,&b);

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            scanf("%c",&ch);

            if (ch!='0' && ch!='1' && ch!='2')
            {
                j--;
                continue;
            }
            else
            {
                if (ch=='0')
                magictable[i][j]=0;
                else if (ch=='1')
                magictable[i][j]=1;
                else
                magictable[i][j]=2;
            }
        }
    }

    scanf("%I64d %I64d %I64d %I64d",&sx,&sy,&ex,&ey);
    s=TwoToOne(sx,sy);
    e=TwoToOne(ex,ey);

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            curver=TwoToOne(i,j);

            nextx=i+1;
            nexty=j;
            if (nextx>=1 && nextx<=n && nexty>=1 && nexty<=m)
            {
                nextver=TwoToOne(nextx,nexty);
                help.ver=nextver;
                help.cost=b;

                if (magictable[i][j]!=magictable[nextx][nexty])
                {
                    help.cost=help.cost+a;
                }

                Graph[curver].push_back(help);
            }

            nextx=i;
            nexty=j+1;
            if (nextx>=1 && nextx<=n && nexty>=1 && nexty<=m)
            {
                nextver=TwoToOne(nextx,nexty);
                help.ver=nextver;
                help.cost=b;

                if (magictable[i][j]!=magictable[nextx][nexty])
                {
                    help.cost=help.cost+a;
                }

                Graph[curver].push_back(help);
            }

            nextx=i-1;
            nexty=j;
            if (nextx>=1 && nextx<=n && nexty>=1 && nexty<=m)
            {
                nextver=TwoToOne(nextx,nexty);
                help.ver=nextver;
                help.cost=b;

                if (magictable[i][j]!=magictable[nextx][nexty])
                {
                    help.cost=help.cost+a;
                }

                Graph[curver].push_back(help);
            }

            nextx=i;
            nexty=j-1;
            if (nextx>=1 && nextx<=n && nexty>=1 && nexty<=m)
            {
                nextver=TwoToOne(nextx,nexty);
                help.ver=nextver;
                help.cost=b;

                if (magictable[i][j]!=magictable[nextx][nexty])
                {
                    help.cost=help.cost+a;
                }

                Graph[curver].push_back(help);
            }
        }
    }

    printf("%I64d\n",Djikstra(s,e));

    return 0;
}
<!-- 0.0405s -->