#include <stdio.h>
#include <stdlib.h>
void print_position(int x, int y);
void print_maze(char **maze, int largura, int altura);
int labirinto(int x_atual, int y_atual, char **maze, int largura, int altura) {
// Se tentou sair do labirinto, este não é o caminho certo.
if (x_atual < 0 || x_atual >= largura || y_atual < 0 || y_atual >= altura) return 0;
char aqui = maze[x_atual][y_atual];
// Verifica se achou a saída.
if (aqui == 'S') return 1;
// Se bateu na parede ou voltou para algum lugar que já esteve,
// então este não é o caminho certo.
if (aqui == 'X' || aqui == '>' || aqui == '<' || aqui == 'v' || aqui == '^') return 0;
// Tenta ir para cima.
maze[x_atual][y_atual] = '^';
if (labirinto(x_atual, y_atual + 1, maze, largura, altura)) return 1;
// Tenta ir para baixo.
maze[x_atual][y_atual] = 'v';
if (labirinto(x_atual, y_atual - 1, maze, largura, altura)) return 1;
// Tenta ir para a esquerda.
maze[x_atual][y_atual] = '<';
if (labirinto(x_atual - 1, y_atual, maze, largura, altura)) return 1;
// Tenta ir para a direita.
maze[x_atual][y_atual] = '>';
if (labirinto(x_atual + 1, y_atual, maze, largura, altura)) return 1;
// Não deu, então volta.
maze[x_atual][y_atual] = 'O';
return 0;
}
int main(void) {
int largura, altura, x_entrada, y_entrada;
scanf("%d %d\n", &largura
, &altura
); char **a
= malloc(largura
* sizeof(char*)); for (int x = 0; x < largura; x++) {
a
[x
] = malloc(altura
* sizeof(char)); }
for (int y = altura - 1; y >= 0; y--) {
for (int x = 0; x < largura; x++) {
if (a[x][y] == 'E') {
x_entrada = x;
y_entrada = y;
}
}
getchar(); //pegar a quebra de linha }
print_maze(a, largura, altura);
labirinto(x_entrada, y_entrada, a, largura, altura);
print_maze(a, largura, altura);
return 0;
}
void print_maze(char **maze, int largura, int altura) {
int x, y;
for (y = altura - 1; y >= 0; y--) {
for (x = 0; x < largura; x++) {
}
}
}
void print_position(int x, int y) {
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnZvaWQgcHJpbnRfcG9zaXRpb24oaW50IHgsIGludCB5KTsKCnZvaWQgcHJpbnRfbWF6ZShjaGFyICoqbWF6ZSwgaW50IGxhcmd1cmEsIGludCBhbHR1cmEpOwoKaW50IGxhYmlyaW50byhpbnQgeF9hdHVhbCwgaW50IHlfYXR1YWwsIGNoYXIgKiptYXplLCBpbnQgbGFyZ3VyYSwgaW50IGFsdHVyYSkgewogICAgLy8gU2UgdGVudG91IHNhaXIgZG8gbGFiaXJpbnRvLCBlc3RlIG7Do28gw6kgbyBjYW1pbmhvIGNlcnRvLgogICAgaWYgKHhfYXR1YWwgPCAwIHx8IHhfYXR1YWwgPj0gbGFyZ3VyYSB8fCB5X2F0dWFsIDwgMCB8fCB5X2F0dWFsID49IGFsdHVyYSkgcmV0dXJuIDA7CgogICAgY2hhciBhcXVpID0gbWF6ZVt4X2F0dWFsXVt5X2F0dWFsXTsKCiAgICAvLyBWZXJpZmljYSBzZSBhY2hvdSBhIHNhw61kYS4KICAgIGlmIChhcXVpID09ICdTJykgcmV0dXJuIDE7CgogICAgLy8gU2UgYmF0ZXUgbmEgcGFyZWRlIG91IHZvbHRvdSBwYXJhIGFsZ3VtIGx1Z2FyIHF1ZSBqw6EgZXN0ZXZlLAogICAgLy8gZW50w6NvIGVzdGUgbsOjbyDDqSBvIGNhbWluaG8gY2VydG8uCiAgICBpZiAoYXF1aSA9PSAnWCcgfHwgYXF1aSA9PSAnPicgfHwgYXF1aSA9PSAnPCcgfHwgYXF1aSA9PSAndicgfHwgYXF1aSA9PSAnXicpIHJldHVybiAwOwoKICAgIC8vIFRlbnRhIGlyIHBhcmEgY2ltYS4KICAgIG1hemVbeF9hdHVhbF1beV9hdHVhbF0gPSAnXic7CiAgICBpZiAobGFiaXJpbnRvKHhfYXR1YWwsIHlfYXR1YWwgKyAxLCBtYXplLCBsYXJndXJhLCBhbHR1cmEpKSByZXR1cm4gMTsKCiAgICAvLyBUZW50YSBpciBwYXJhIGJhaXhvLgogICAgbWF6ZVt4X2F0dWFsXVt5X2F0dWFsXSA9ICd2JzsKICAgIGlmIChsYWJpcmludG8oeF9hdHVhbCwgeV9hdHVhbCAtIDEsIG1hemUsIGxhcmd1cmEsIGFsdHVyYSkpIHJldHVybiAxOwoKICAgIC8vIFRlbnRhIGlyIHBhcmEgYSBlc3F1ZXJkYS4KICAgIG1hemVbeF9hdHVhbF1beV9hdHVhbF0gPSAnPCc7CiAgICBpZiAobGFiaXJpbnRvKHhfYXR1YWwgLSAxLCB5X2F0dWFsLCBtYXplLCBsYXJndXJhLCBhbHR1cmEpKSByZXR1cm4gMTsKCiAgICAvLyBUZW50YSBpciBwYXJhIGEgZGlyZWl0YS4KICAgIG1hemVbeF9hdHVhbF1beV9hdHVhbF0gPSAnPic7CiAgICBpZiAobGFiaXJpbnRvKHhfYXR1YWwgKyAxLCB5X2F0dWFsLCBtYXplLCBsYXJndXJhLCBhbHR1cmEpKSByZXR1cm4gMTsKCiAgICAvLyBOw6NvIGRldSwgZW50w6NvIHZvbHRhLgogICAgbWF6ZVt4X2F0dWFsXVt5X2F0dWFsXSA9ICdPJzsgICAKICAgIHJldHVybiAwOwp9CgppbnQgbWFpbih2b2lkKSB7CiAgICBpbnQgbGFyZ3VyYSwgYWx0dXJhLCB4X2VudHJhZGEsIHlfZW50cmFkYTsKICAgIHNjYW5mKCIlZCAlZFxuIiwgJmxhcmd1cmEsICZhbHR1cmEpOwogICAgY2hhciAqKmEgPSBtYWxsb2MobGFyZ3VyYSAqIHNpemVvZihjaGFyKikpOwogICAgZm9yIChpbnQgeCA9IDA7IHggPCBsYXJndXJhOyB4KyspIHsKICAgICAgICBhW3hdID0gbWFsbG9jKGFsdHVyYSAqIHNpemVvZihjaGFyKSk7CiAgICB9CiAgICBmb3IgKGludCB5ID0gYWx0dXJhIC0gMTsgeSA+PSAwOyB5LS0pIHsKICAgICAgICBmb3IgKGludCB4ID0gMDsgeCA8IGxhcmd1cmE7IHgrKykgewogICAgICAgICAgICBhW3hdW3ldID0gZ2V0Y2hhcigpOwogICAgICAgICAgICBpZiAoYVt4XVt5XSA9PSAnRScpIHsKICAgICAgICAgICAgICAgIHhfZW50cmFkYSA9IHg7CiAgICAgICAgICAgICAgICB5X2VudHJhZGEgPSB5OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGdldGNoYXIoKTsgLy9wZWdhciBhIHF1ZWJyYSBkZSBsaW5oYQogICAgfQogICAgcHJpbnRmKCJFbnRyYWRhOlxuIik7CiAgICBwcmludF9tYXplKGEsIGxhcmd1cmEsIGFsdHVyYSk7CiAgICBsYWJpcmludG8oeF9lbnRyYWRhLCB5X2VudHJhZGEsIGEsIGxhcmd1cmEsIGFsdHVyYSk7CiAgICBwcmludGYoIlxuU2HDrWRhOlxuIik7CiAgICBwcmludF9tYXplKGEsIGxhcmd1cmEsIGFsdHVyYSk7CiAgICByZXR1cm4gMDsKfQoKdm9pZCBwcmludF9tYXplKGNoYXIgKiptYXplLCBpbnQgbGFyZ3VyYSwgaW50IGFsdHVyYSkgewogICAgaW50IHgsIHk7CiAgICBmb3IgKHkgPSBhbHR1cmEgLSAxOyB5ID49IDA7IHktLSkgewogICAgICAgIGZvciAoeCA9IDA7IHggPCBsYXJndXJhOyB4KyspIHsKICAgICAgICAgICAgcHJpbnRmKCIlYyIsIG1hemVbeF1beV0pOwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CiAgICB9Cn0KCnZvaWQgcHJpbnRfcG9zaXRpb24oaW50IHgsIGludCB5KSB7CiAgICBwcmludGYoIiglZCwgJWQpIiwgeCwgeSk7Cn0=