Recentemente, houve uma neve grande e minha entrada de automóveis precisa de neve. Se o soprador de neve passar por alguma área que já tenha soprado, essa área terá soprado neve e precisará ser soprado novamente. E, é claro, o soprador de neve não pode começar no meio da entrada da garagem, ele precisa começar na minha garagem, onde está guardado.

Mais formalmente:

Seu programa usa uma forma padrão de entrada como uma string ou matriz multidimensional que se parece com o seguinte:

XXXXOOOOXXXX
X          X
X          X
XXXXXXXXXXXX

Xrepresenta uma área que não pode ser explodido-neve, Orepresenta uma área, onde o ventilador de neve pode ser implantado, e espaços vazios representam áreas onde há neve. Você pode escolher valores diferentes, se desejar.

Seu programa deve gerar algo como o seguinte:

XXXX*%OOXXXX
Xv<<<^<<<<<X
X>>>>>>>>>^X
XXXXXXXXXXXX

O soprador de neve começa no *. O *sempre aponta para o espaço não-garagem mais próximo. A <, >, v, e ^todos representam indicações de onde a próxima instrução é. Eles apontam o soprador de neve para onde ir. Quando um ponteiro aponta para o %, o ventilador voltou à garagem e toda a entrada de automóveis deve estar limpa.

O soprador de neve deve passar por toda a entrada de automóveis. O caminho do soprador de neve nunca pode se sobrepor. Entrada impossível não deve ser fornecida.

Como eu não quero ficar fora mais do que preciso e não preciso gastar muito tempo digitando, o programa deve ser o mais curto possível. O código mais curto vence!

Casos de teste:

Esses casos de teste podem ter várias respostas corretas. Forneci soluções possíveis abaixo de cada caso de teste.

Caso de teste 1: aquele fornecido no exemplo.

Caso de teste 2:

XOOOOOX
X     X
X     X
X     XXXXXXXX
X            X
X            X
XXXXXXXXXXXXXX

X*OOO%X
Xv>>>^X
Xv^<<<X
Xv>>>^XXXXXXXX
Xv^<<<<<<<<<<X
X>>>>>>>>>>>^X
XXXXXXXXXXXXXX

Caso de teste 3:

XOOOOX
X    X
X    X
X  XXX
X    X
X    X
XXXXXX

XOO%*X
X>>^vX
X^v<<X
X^vXXX
X^>>vX
X^<<<X
XXXXXX

Caso de teste 4:

XXXXXXXXXXXXX
O           X
O    X      X
O    X      X
O           X
XXXXXXXXXXXXX

XXXXXXXXXXXXX
*>>>>>>>>>>vX
Ov<v<Xv<<<<<X
Ov^v^X>>>>>vX
%<^<^<<<<<<<X
XXXXXXXXXXXXX

JavaScript (ES6), 346 310 299 298 297 296 283 bytes

f=(a,y=0,x=0)=>(a[y][x]?a[y][x]=='O'&&(a[y][x]='*',(g=w=>(w=a[y])&&w[x]&&(w[x]<'!'?g(w[x]='v',y++)||g(w[x++]='>',y--)||g(w[--x]='^',y--)||g(w[x--]='<',y++)||+(w[++x]=' '):w[x]=='O'&&!/ /.test(a)?w[x]='%':0))(y++)||g(y-=2)||g(y++,x++)||g(x-=2)||+(a[y][++x]='O'))||f(a,y,x+1):f(a,y+1))

<textarea id="tests">XXXXOOOOXXXX&#10;X          X&#10;X          X&#10;XXXXXXXXXXXX&#10;&#10;XOOOOOX&#10;X     X&#10;X     X&#10;X     XXXXXXXX&#10;X            X&#10;X            X&#10;XXXXXXXXXXXXXX&#10;&#10;XOOOOX&#10;X    X&#10;X    X&#10;X  XXX&#10;X    X&#10;X    X&#10;XXXXXX&#10;&#10;XXXXXXXXXXXXX&#10;O           X&#10;O    X      X&#10;O    X      X&#10;O           X&#10;XXXXXXXXXXXXX</textarea><br><button onclick="for(test of document.getElementById('tests').value.split('\n\n')){console.log(test);arr=test.split('\n').map(line=>line.split(''));f(arr);console.log(arr.map(line=>line.join('')).join('\n'))}">Run</button>

Muito hacky em alguns lugares, mas eu queria divulgar o código. Entrada como uma matriz de caracteres 2D, saída modificando a referida matriz.

Versão ungolfed

Este é o mesmo algoritmo exato, exceto por alguns truthy / magic Falsas com +' 'estar NaNsendo Falsas (e mais alguns), algumas variáveis golfe e usando ifs, em vez de ?:, ||e &&.

f = (a, y = 0, x = 0) => {         // main function
  if (!a[y][x])                    // check for end of line
    return f(a, y + 1);            // end of line, recursively check next
  if (a[y][x] == 'O') {            // check for valid start position
    a[y][x] = '*';                 // set the start position
    function g() {                 // pathfinder function
      if (!a[y] || !a[y][x])       // check for out of bounds
        return 0;
      if (a[y][x] == ' ') {        // check for snow
        a[y][x] = 'v';             // set current cell to 'down'
        y++;                       // move position down
        if (g()) return 1;         // see if a valid route is found from there
        y--;                       // if not, reset position and try again
        a[y][x] = '>';             // repeat for other directions
        x++;
        if (g()) return 1;
        x--;
        a[y][x] = '^';
        y--;
        if (g()) return 1;
        y++;
        a[y][x] = '<';
        x++;
        if (g()) return 1;
        x++;
        a[y][x] = ' ';             // no route found, reset cell to snow
        return 0;
      }
      if (a[y][x] == 'O'           // check for valid exit
          && !/ /.test(a)) {       // and that no snow is left
        a[y][x] = '%';             // set the exit
        return 1;
      }
    }
    y++;                           // move a cell down from the start position
    if (g()) return 1;             // see if a valid route starts there
    y -= 2;                        // repeat for other directions
    if (g()) return 1;
    y++; x++;
    if (g()) return 1;
    x -= 2;
    if (g()) return 1;
    x++;
    a[y][x] = 'O';                 // no route found, continue on
  }
  return f(a, y, x + 1);           // check the next cell
}