#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <functional>#include <queue>using namespace std;typedef long long LL;const int INF = 0x7f7f7f7f;const int dir[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };const int N = 110;char g[110][110];int w, h, p1, p2;int n, edge, dis[N][N][4];struct point { int x, y, k; point() { } point(int x, int y, int k) : x(x), y(y), k(k) { }};void bfs() { queue<point> q; memset(dis, 0x7f, sizeof(dis)); if (g[h][1] == 'b') { return; } for (int i = 0; i < 3; i++) { int cost; if (i == 1) { cost = p1; } else { cost = p2; } q.push(point(h, 1, i)); dis[h][1][i] = cost; } while (!q.empty()) { point u = q.front(); q.pop(); int dd = u.k; int dx = u.x + dir[dd][0]; int dy = u.y + dir[dd][1]; if (dx > 0 && dx <= h && dy > 0 && dy <= w && g[dx][dy] != 'b') { for (int i = 0; i < 4; i++) { int cost; if ((i + 2) % 4 == dd) continue; if (i == dd) { cost = p1; } else { cost = p2; } if (dis[dx][dy][i] > dis[u.x][u.y][u.k] + cost) { dis[dx][dy][i] = dis[u.x][u.y][u.k] + cost; q.push(point(dx, dy, i)); } } } }}int main() { while (~scanf("%d%d%d%d", &w, &h, &p1, &p2)) { getchar(); for (int i = 1; i <= h; i++) { gets(g[i] + 1); } bfs(); if (dis[1][w][1] < INF) { printf("%dn", dis[1][w][1]); } else { printf("impossiblen"); } } return 0;}
