The depth-first search algorithm explores a graph by going as far as possible along each branch before backtracking. Implemented recursively, DFS uses the call stack to manage backtracking automatically. The strategy aligns with the adage: persist untill a dead end is reached, then retreat to explore alternative paths.

Consider a binary tree where each node has left and right children. The goal is locating a target node starting from the root. The traversal prioritizes the left subtree; if unproductive, it proceeds to the right. Mark nodes as visited to avoid cycles.

Example: Find node X starting at S in the tree below:

    S
   / \
  T   U
 / \   \
V   W   X

Traversal sequence:

• Begin at S, move to left child T.
• From T, move to left child V (leaf). Dead end: backtrack to T.
• At T, move to right child W (leaf). Dead end: backtrack to T, then to S.
• At S, move to right child U.
• From U, move to right child X (target found).

This pattern generalizes to graphs via adjacency exploration. Each node is processed by recursive visiting its neighbors. Backtracking occurs when all neighbor are exhausted.

Maze Reachability Check

Given a grid of size rows by cols, determine if a path exists from top-left (1,1) to bottom-right (rows, cols). Cells marked '.' are traversable; others block movement. Four-directional moves (up, down, left, right) are allowed.

Represent the grid as a 2D array. Maintain a visited matrix to prevent revisiting cells.

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAX_DIM = 50;
int rows, cols;
char grid[MAX_DIM][MAX_DIM];
bool visited[MAX_DIM][MAX_DIM];

// Direction vectors: up, down, left, right
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

void explore(int r, int c) {
    if (r == rows && c == cols) {
        cout << "YES" << endl;
        exit(0);
    }

    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 1 && nr <= rows && nc >= 1 && nc <= cols) {
            if (!visited[nr][nc] && grid[nr][nc] == '.') {
                visited[nr][nc] = true;
                explore(nr, nc);
            }
        }
    }
}

int main() {
    cin >> rows >> cols;
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            cin >> grid[i][j];
        }
    }

    visited[1][1] = true;
    explore(1, 1);

    cout << "NO" << endl;
    return 0;
}

Counting Paths in a Maze

Given a grid with obstacles, count distinct paths from start (sr, sc) to end (er, ec) without revisiting cells. Obstacles are marked in a separate grid.

#include <iostream>
using namespace std;

const int MAX_SIZE = 50;
int rows, cols, obsCount;
int pathCount = 0;
int obstacleGrid[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];

// Directions: up, down, left, right
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

void traverse(int r, int c, int er, int ec) {
    if (r == er && c == ec) {
        pathCount++;
        return;
    }

    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 1 && nr <= rows && nc >= 1 && nc <= cols) {
            if (!visited[nr][nc] && obstacleGrid[nr][nc] == 0) {
                visited[nr][nc] = true;
                traverse(nr, nc, er, ec);
                visited[nr][nc] = false; // backtrack
            }
        }
    }
}

int main() {
    int sr, sc, er, ec;
    cin >> rows >> cols >> obsCount;
    cin >> sr >> sc >> er >> ec;

    for (int i = 0; i < obsCount; ++i) {
        int r, c;
        cin >> r >> c;
        obstacleGrid[r][c] = 1; // mark obstacle
    }

    visited[sr][sc] = true;
    traverse(sr, sc, er, ec);
    cout << pathCount << endl;
    return 0;
}