A busca em profundidade (DFS) é um algoritmo fundamental para explorar grafos e árvores. Sua ideia cantral é percorrer um caminho até o fim antes de retroceder. Visualmente, podemos imaginar um labirinto inclinado a 45 graus que se transforma em uma estrutura arbórea.

Considere um ponto de partida 1: a DFS seguirá por uma única rota até o limite, como nos exemplos abaixo:

1 → 2 → 3 → 6
1 → 2 → 3 → 5
1 → 2 → 4 → 8
1 → 2 → 4 → 7

O algoritmo inicia no nó raiz e avança por cada ramo até não haver mais vizinhos não visitados. Quando isso ocorre, ele retorna ao nó anterior para explorar outras direções.

Implementação com Pilha

A implementação mais direta utiliza uma pilha explícita. O processo é:

• Insira o pontto inicial na pilha
• Enquanto a pilha não estiver vazia, examine os vizinhos seguindo uma ordem de direções
• Se um vizinho é válido (dentro dos limites, não é obstáculo, não foi visitado), empilhe-o e marque como visitado
• Se nenhum vizinho for válido, desempilhe o nó atual (retrocesso)

No código abaixo, a matriz M representa o labirinto (1 indica obstáculo), e vis controla as células já exploradas. O vetor N atua como pilha, com top sendo o índice do topo.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=100;
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={1,1,1,0,0,-1,-1,-1};
struct Node {
    int x, y;
    int idx;
} N[maxn];
int M[maxn][maxn];
bool vis[maxn][maxn];
int top = 0;

int main() {
    freopen("1.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            scanf("%d",&M[i][j]);

    top = 1;
    N[top] = Node{0,0,-1};

    while (top != 0) {
        int d = -1;
        while ((++d) < 8) {
            int xx = N[top].x + dx[d];
            int yy = N[top].y + dy[d];
            if (xx<0 || xx>=n || yy<0 || yy>=n || M[xx][yy]==1 || vis[xx][yy]==1)
                continue;
            N[++top].x = xx;
            N[top].y = yy;
            N[top].idx = d;
            vis[xx][yy] = 1;
            M[xx][yy] = 1;
            break;
        }
        if (d == 8) --top;
        if (N[top].x == n-1 && N[top].y == n-1) break;
    }

    for (int i=1; i<=top; ++i)
        printf("%d %d\n", N[i].x, N[i].y);
    return 0;
}
/*
5
0 1 1 1 1
1 0 1 1 1
0 1 0 1 1
0 1 1 1 1
0 0 0 0 0
*/

Observação sobre o Controle de Direções

Um detalhe sutil no código acima é o uso de d = -1 seguido de while ((++d) < 8). Isso equivale a percorrer d de 0 a 7. Se fizéssemos d = 0 e while (d < 8) { ++d; }, apenas os valores 1 a 7 seriam testados, ignorando a direção 0. Por outro lado, while (d < 9) { ++d; } levaria a d = 8, causando acesso fora dos limites do vetor.

Uma abordagem alternativa mais robusta é armazenar a última direção testada em cada nó, como na versão revisada abaixo:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=100;
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={1,1,1,0,0,-1,-1,-1};
struct Node {
    int x, y;
    int idx;
} N[maxn];
int M[maxn][maxn];
bool vis[maxn][maxn];
int top = 0;

int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            scanf("%d",&M[i][j]);

    top = 1;
    N[top].x = 0;
    N[top].y = 0;
    N[top].idx = -1;

    while (top != 0) {
        int d = ++N[top].idx;
        if (d < 8) {
            int xx = N[top].x + dx[d];
            int yy = N[top].y + dy[d];
            if (xx<0 || xx>=n || yy<0 || yy>=n || M[xx][yy]==1 || vis[xx][yy]==1)
                continue;
            N[++top].x = xx;
            N[top].y = yy;
            N[top].idx = -1;
            vis[xx][yy] = 1;
            M[xx][yy] = 1;
        } else {
            top--;
        }
        if (N[top].x == n-1 && N[top].y == n-1) break;
    }

    for (int i=1; i<=top; ++i)
        printf("%d %d\n", N[i].x, N[i].y);
    return 0;
}
/*
5
0 1 1 1 1
1 0 1 1 1
0 1 0 1 1
0 1 1 1 1
0 0 0 0 0
*/

Nesta versão, cada nó guarda em idx a última direção testada. Ao acessar um nó, incrementamos idx para testar a próxima direção. Quando todas as 8 direções foram esgotadas (d == 8), o nó é desempilhado. O novo nó inserido começa com idx = -1, garantindo que as direções sejam testadas a partir de 0.