#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <time.h>
#include <windows.h>
#include <queue>
#define RAN(x) rand()%x
#define MAX(x,y) x>y?x:y
#define PO(x,y) (x*m+y)
#define tox(x) (x/m)
#define toy(x) (x%m)
#define ABS(x) (x>0?x:-x)
using namespace std;
const int MAX_N = 205;
double ALPHA = 1.0;
struct NODE{
    int X,Y;
    NODE(int x,int y){X = x;Y = y;}
    ~NODE(){}
    NODE operator +(const NODE B){
        return NODE(X+B.X,Y+B.Y);
    }
    bool operator ==(const NODE B){
        return X==B.X&&Y==B.Y;
    }
};

typedef struct line{
    int x_1,x_2,y_1,y_2;
    int id; 
    line(){}
    line(int X1, int Y1, int X2, int Y2, int d){
        id = d;
        x_1 = X1,x_2 =X2,y_1 = Y1,y_2 = Y2;
    }
    ~line(){}
}LINE;

int pa[MAX_N*MAX_N];
int find(int x){if(pa[x]==x)return x;return find(pa[x]);}
void unit(int x,int y){int x_1 = find(x);int y_1 = find(y);pa[y_1]=x_1;}

LINE map[MAX_N*MAX_N*2];
bool VIS[MAX_N*MAX_N*2];
int n,m,num;

queue<int> ans;
uint8_t bitmap[MAX_N * 2][MAX_N * 2];
void init(){
    for(int i = 0 ; i<m*n; i++){pa[i]=i;VIS[i] = 0;}
    num = 0;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m-1;j++){
            map[num] = LINE(i,j,i,j+1,num);num++;
        }
    }
    for(int i = 0; i<n-1; i++){
        for(int j = 0; j<m;j++){
            map[num] = LINE(i,j,i+1,j,num);num++;
        }
    }
}

/*This is just a krus algo, a simple krus algo*/
void krus(){
    int NUM = n*m-1;
    while(NUM){
        int po = RAN(num);
        if(!VIS[po]){
            if(find(map[po].x_1*m+map[po].y_1)!=find(map[po].x_2*m+map[po].y_2)){
                unit(map[po].x_1*m+map[po].y_1, map[po].x_2*m+map[po].y_2);
                ans.push(po);
                NUM--;
            }
            VIS[po] = 1;
        }
    }
}
void tobitmap(){
    queue<int> anst = ans;
    for(int i = 0; i < 2 * n + 1; i++){
        bitmap[i][0] = 1;
        bitmap[i][2 * n] = 1;
        
    }
    for(int i = 0; i < 2 * m + 1; i++){
        bitmap[0][i] = 1;
        bitmap[2 * m][i] = 1;
    }
    for(int i = 1; i < n + 1; i++){
        for(int j = 1; j < m + 1; j++){
            bitmap[2*i][j*2-1] = 1;
            bitmap[2*i-1][j*2] = 1;
            bitmap[2*i][j*2] = 1;
            bitmap[2*i - 1][j*2 - 1] = 0;
        }
    }
    while(!anst.empty()){
        LINE T = map[anst.front()];anst.pop();
        bitmap[T.x_1+T.x_2 + 1][T.y_1+T.y_2 + 1] = 0;
    }
    bitmap[1][0] = 2;
    bitmap[2 * n - 1][2 * m] = 2;
}
/*PAINTER*/
void stdPAINT(){
    HANDLE handle;
    handle = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD coord;coord.X = 0;coord.Y = 0;
    SetConsoleCursorPosition(handle, coord);
    SetConsoleTextAttribute(handle, BACKGROUND_BLUE | FOREGROUND_INTENSITY);
    for(int i = 0; i < n*2+1; i++){
        for(int j = 0; j < m*2+1; j++){
            switch(bitmap[i][j]){
                case 0:{SetConsoleTextAttribute(handle, BACKGROUND_INTENSITY | FOREGROUND_INTENSITY);printf(" ");break;}
                case 1:{SetConsoleTextAttribute(handle, BACKGROUND_BLUE | FOREGROUND_INTENSITY);printf("+");break;}
                case 2:{SetConsoleTextAttribute(handle, BACKGROUND_GREEN | FOREGROUND_INTENSITY);printf(">");break;}
                case 3:{SetConsoleTextAttribute(handle, BACKGROUND_RED | FOREGROUND_INTENSITY);printf(" ");break;}
                default:{break;}
            }
        }
        printf("\n");
    }
}
void bitmapPAINT(int height, int width, const char *file_name){
    FILE *map = fopen(file_name,"wb");
    BITMAPFILEHEADER bf;
    BITMAPINFOHEADER bi;
    bf.bfType = 0x4D42;
    bf.bfSize = height*width*3*20*20;
    bf.bfReserved1 = 0;
    bf.bfReserved2 = 0;
    bf.bfOffBits = 54;
    bi.biSize = 40;
    bi.biHeight = height*20;
    bi.biWidth = width*20;
    bi.biPlanes = 1;
    bi.biXPelsPerMeter = 0;
    bi.biYPelsPerMeter = 0;
    bi.biBitCount = 24;
    bi.biSizeImage = height*width*3*20*20;
    bi.biClrUsed = 0;
    bi.biCompression = 0;
    bi.biClrImportant = 0;
    fwrite(&bf,sizeof(bf),1,map);
    fwrite(&bi,sizeof(bi),1,map);
    uint8_t *img = new uint8_t[3];
    for(int i = 0; i < height; i++){
        for(int k = 0;k < 20; k++){
            for(int j = 0; j < width; j++){
                switch(bitmap[i][j]){
                    case 0:{img[0] = 255;img[1] = 255;img[2] = 255;break;}
                    case 1:{img[0] = 0;img[1] = 0;img[2] = 0;break;}
                    case 2:{img[0] = 0;img[1] = 127;img[2] = 0;break;}
                    case 3:{img[0] = 0;img[1] = 127;img[2] = 127;break;}
                    default:{break;}
                }
                for(int l = 0; l < 20; l++)fwrite(img, sizeof(uint8_t)*3, 1, map);
            }
        }
    }
}

/*Next is the training progress, unfinished*/
int head[MAX_N*MAX_N], Next[MAX_N*MAX_N*2], V[MAX_N*MAX_N*2], dep[MAX_N*MAX_N], avis[MAX_N*MAX_N];
int tot;
int pre[MAX_N*MAX_N];
void init2(){
    tot = 0;memset(avis,0,sizeof(avis)); 
}
int add(int a, int b){
    V[++tot] = b;Next[tot] = head[a];head[a] = tot;
}
int bfs(){
    queue<int> MAP = ans;
    while(!MAP.empty()){LINE x = map[MAP.front()];MAP.pop();add(PO(x.x_1,x.y_1),PO(x.x_2,x.y_2));add(PO(x.x_2,x.y_2),PO(x.x_1,x.y_1));}
    MAP.push(0);dep[0] = 0;avis[0] = 1;
    while(!MAP.empty()){
        int x = MAP.front();MAP.pop();
        for(int i = head[x]; i; i = Next[i]){
            if(!avis[V[i]]){
                MAP.push(V[i]);
                dep[V[i]] = dep[x]+1;
                pre[V[i]] = x;
                avis[V[i]] = 1; 
                if(V[i]==PO((n-1),(m-1))){
                    return dep[V[i]];
                }
            }
        }
    }
}

void dfsinit(){
    queue<int> MAP = ans;
    while(!MAP.empty()){LINE x = map[MAP.front()];MAP.pop();add(PO(x.x_1,x.y_1),PO(x.x_2,x.y_2));add(PO(x.x_2,x.y_2),PO(x.x_1,x.y_1));}
    return;
}
int dfs(int x){
    for(int i = head[x]; i; i = Next[i]){
            if(!avis[V[i]]){
                dep[V[i]] = dep[x]+1;
                avis[V[i]] = 1;
                pre[V[i]] = x;
                if(V[i]==PO((n-1),(m-1))){
                    return dep[V[i]];
                }
                int t = dfs(V[i]);
                if(t)return t;
            }
        }
    return 0;
}

void Rerender(){
    pre[0] = 0;
    for(int i = (n-1)*m + m - 1, j = pre[i]; i!=0; i = j, j = pre[j]){
        bitmap[tox(i)*2 + 1][toy(i)*2 + 1] = 3;
        bitmap[tox(j)+tox(i) + 1][toy(j)+toy(i) + 1] = 3;
        bitmap[tox(j)*2 + 1][toy(j)*2 + 1] = 3;
    }
}
/*MAIN*/
char filename[255];
int main(){
    srand(time(NULL));
    scanf("%d%d",&n,&m);
    scanf("%s",filename);
    init();
    krus();
    dfsinit();
    int step = dfs(0);
    tobitmap();
    Rerender();
    stdPAINT();
    bitmapPAINT(2 * n + 1, 2 * m + 1, filename);
    printf("\n|step : %d |\n", step);
    system("pause");
    return 0;
}