#include <stdio.h>


#define MARCA   500
#define BAIXO   501
#define CIMA    502
#define DIR     503
#define ESQ     504

#define PASSOU  2


int mazze[50][50] ;
int caminho[500], ultimo; // caminho percorrido;
int nlin, ncol; // numero de linhas e colunas

int main()
{
    int i, j; // auxiliares
    int curl, curc; // posicao corrente

    // le as dimensões do labirinto
    printf("Numero de linhas: ");
    scanf("%d", &nlin);
    printf("Numero de colunas: ");
    scanf("%d", &ncol);

    // le as posições do labirinto
    // assume que as posições nao inicializadas são 0
    // considera que as bordas nao sao navegaveis
    for (i = 1; i <= nlin; i++)
        for (j = 1; j <= ncol; j++)
           scanf("%d", &mazze[i][j]);

    // inicializa posicao corrent
    curl = curc = 1;
    ultimo = 0;

    while ( curl != nlin || curc != ncol )
    { // continua até chegar na saida

        //printf("Corrente %d %d\n", curl, curc);

        // registra posicao atual como parte do caminho
        caminho[ultimo++] = curl;
        caminho[ultimo++] = curc;

        // marca posicao atual com ja trilhada
        mazze[curl][curc] = PASSOU;

        if (mazze[curl+1][curc] == 1 )
        {
            curl++; // vai para baixo
        }
        else
        if (mazze[curl][curc+1] == 1 )
        {
            curc++; // vai para a direita
        }
        else
        if (mazze[curl-1][curc] == 1 )
        {
            curl--; // vai para cima
        }
        else
        if (mazze[curl][curc-1] == 1 )
        {
            curc--; // vai para a esquerda
        }
        else
        { // nehum vizinho habilitado
            // retira a posição atual do caminho
            ultimo -= 2;
            mazze[curl][curc] = -1;

            // se aida ha posicoes para retornar
            if ( ultimo > 0 )
            {   // recupera o ultimo elemento que esta no caminho solucao
                curc = caminho[--ultimo];
                curl = caminho[--ultimo];
            }
            else
            { // nesse caso nao ha mais elementos para voltar no caminho
                printf("Nao ha solucao :-(\n");
                return 0;
            }
        }
    }
    // posicao de saida faz parte do caminho
    caminho[ultimo++] = curl;
    caminho[ultimo++] = curc;

    // marca o caminho percorrido
    for (i = 0; i < ultimo; i += 2)
    {
        mazze[caminho[i]][caminho[i+1]] = MARCA;
    }

    // imprime * no caminho marcado
    printf("\n");
    for (i = 1; i <= nlin; i++)
    {
        for (j = 1; j <= ncol; j++)
        {
           if ( mazze[i][j] == MARCA )
                printf("%c ", '*');
            else
                printf("%c ", '_');
        }
        printf("\n");
    }

    // marca de novo o caminho percorrido com V, <, > ou ^
    for (i = 0; i < ultimo-2; i += 2)
    {
        int m, pl, pc;

        // pega próximo elemento no caminho para ver qual foi o
        // movimento realizado
        pl = caminho[i+2];
        pc = caminho[i+3];
        curl = caminho[i];
        curc = caminho[i+1];

        // se a proxima linha for maior q a atual então foi V
        if (pl > curl)
            m = BAIXO;
        else
        // se a proxima linha for menor q a atual então foi ^
        if (pl < curl)
            m = CIMA;
        else
        // se a proxima coluna for maior q a atual então foi >
        if (pc > curc)
            m = DIR;
        else
        // se a proxima coluna for menor q a atual então foi <
        if (pc < curc)
            m = ESQ;

        // marca o movimento na matriz
        mazze[caminho[i]][caminho[i+1]] = m;
    }
    // marco o movimento da ultima posicao, sempre pra baixo
    mazze[caminho[i]][caminho[i+1]] = BAIXO;

    // imprime o caminho marcado, de acordo com os movimentos
    printf("\n");
    for (i = 1; i <= nlin; i++)
    {
        for (j = 1; j <= ncol; j++)
        {
            switch (mazze[i][j])
            {
                case DIR:
                    printf("%c ", '>');
                    break;
                case ESQ:
                    printf("%c ", '<');
                    break;
                case BAIXO:
                    printf("%c ", 'V');
                    break;
                case CIMA:
                    printf("%c ", '^');
                    break;
                default:
                    printf("%c ", '_');
                    break;
            }
        }
        printf("\n");
    }

    return 0;
}