Problem 1: Dual Container Water Measurement

This classic state-space search problem involves two containers with known capacities and an infinite water supply. The goal is to achieve a specific volume in one container through a series of operations.

Problem Analysis

The key insight is representing each state by the current water volumes in both containers. Since we need to reconstruct the solution path, we must track the sequence of operations performed.

Rather than storing full operation strings at each state (which is memory-intensive), we encode operations as integers and maintain a lookup table of operation names. Each state records its (volumeA, volumeB) pair and the operation sequence that led to it.

Implementation Strategy

• Define a State structure containing water volumes and operation history
• Use a queue for BFS traversal and a 2D boolean array to track visited states
• Generate six possible operations from each state: fill A, empty A, fill B, empty B, pour A→B, pour B→A
• Terminate when target volume is achieved in container B

#include <iostream>
#include <queue>
#include <string>
#include <vector>

const int MAX_CAPACITY = 1005;

struct State {
    int volA, volB;
    std::string moves;
    
    State(int a, int b) : volA(a), volB(b) {}
    State(int a, int b, const std::string& m) : volA(a), volB(b), moves(m) {}
};

std::string operations[6] = {
    "fill A", "empty A", "fill B", "empty B", 
    "pour A B", "pour B A"
};

int capacityA, capacityB, targetVol;
State initial(0, 0);
bool visited[MAX_CAPACITY][MAX_CAPACITY];

void solveWaterJug() {
    std::queue<State> q;
    q.push(initial);
    visited[0][0] = true;
    
    while (!q.empty()) {
        State current = q.front();
        q.pop();
        
        if (current.volB == targetVol) {
            for (char moveCode : current.moves) {
                std::cout << operations[moveCode - '0'] << std::endl;
            }
            std::cout << "success" << std::endl;
            return;
        }
        
        // Fill container A
        if (!visited[capacityA][current.volB]) {
            visited[capacityA][current.volB] = true;
            q.push(State(capacityA, current.volB, current.moves + "0"));
        }
        
        // Empty container A
        if (!visited[0][current.volB]) {
            visited[0][current.volB] = true;
            q.push(State(0, current.volB, current.moves + "1"));
        }
        
        // Fill container B
        if (!visited[current.volA][capacityB]) {
            visited[current.volA][capacityB] = true;
            q.push(State(current.volA, capacityB, current.moves + "2"));
        }
        
        // Empty container B
        if (!visited[current.volA][0]) {
            visited[current.volA][0] = true;
            q.push(State(current.volA, 0, current.moves + "3"));
        }
        
        // Pour from A to B
        int availableInB = capacityB - current.volB;
        if (current.volA >= availableInB) {
            int newA = current.volA - availableInB;
            if (!visited[newA][capacityB]) {
                visited[newA][capacityB] = true;
                q.push(State(newA, capacityB, current.moves + "4"));
            }
        } else {
            int newB = current.volB + current.volA;
            if (!visited[0][newB]) {
                visited[0][newB] = true;
                q.push(State(0, newB, current.moves + "4"));
            }
        }
        
        // Pour from B to A
        int availableInA = capacityA - current.volA;
        if (current.volB >= availableInA) {
            int newB = current.volB - availableInA;
            if (!visited[capacityA][newB]) {
                visited[capacityA][newB] = true;
                q.push(State(capacityA, newB, current.moves + "5"));
            }
        } else {
            int newA = current.volA + current.volB;
            if (!visited[newA][0]) {
                visited[newA][0] = true;
                q.push(State(newA, 0, current.moves + "5"));
            }
        }
    }
}

int main() {
    while (std::cin >> capacityA >> capacityB >> targetVol) {
        memset(visited, 0, sizeof(visited));
        solveWaterJug();
    }
    return 0;
}

Problem 2: Grid Navigation with Dynamic Obstacles

This problem involves navigating an 8×8 grid where obstacles fall downward each time step. The challenge is that the environment changes based on the search depth, requiring careful state management.

Key Considerations

• Standing still is a valid move
• The grid configuration changes with each BFS level, so standard visited arrays are ineffective
• Each state must track its depth to synchronize obstacle movement
• Obstacles must be updated from bottom to top to prevent propagation errors
• If depth reaches 8, all obstacles have fallen, guaranteeing a clear path

Implementation Details

The critical insight is decoupling obstacle updates from node expansion. We maintain a currentLevel variable and only advance obstacles when processing nodes from the next depth level.

#include <iostream>
#include <queue>
#include <cstring>

struct Position {
    int row, col;
    int depth;
};

char grid[8][8];
int dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
int dy[9] = {0, 0, -1, 1, -1, 1, -1, -1, 0};

bool isSafe(int x, int y) {
    if (x < 0 || x >= 8 || y < 0 || y >= 8) return false;
    if (grid[x][y] == 'S') return false;
    if (x > 0 && grid[x-1][y] == 'S') return false;
    return true;
}

void dropObstacles() {
    for (int i = 7; i >= 0; --i) {
        for (int j = 0; j < 8; ++j) {
            if (grid[i][j] == 'S') {
                grid[i][j] = '.';
                if (i + 1 < 8) grid[i+1][j] = 'S';
            }
        }
    }
}

bool navigateGrid(Position start, Position target) {
    std::queue<Position> q;
    q.push(start);
    int currentLevel = 0;
    
    while (!q.empty()) {
        Position current = q.front();
        q.pop();
        
        if (current.depth > currentLevel) {
            dropObstacles();
            currentLevel = current.depth;
        }
        
        if ((current.row == target.row && current.col == target.col) || 
            current.depth >= 8) {
            return true;
        }
        
        for (int i = 0; i < 9; ++i) {
            int newX = current.row + dx[i];
            int newY = current.col + dy[i];
            
            if (isSafe(newX, newY)) {
                q.push({newX, newY, current.depth + 1});
            }
        }
    }
    return false;
}

Problem 3: Sliding Tile Puzzle (8-Puzzle)

The 8-puzzle consists of a 3×3 grid with 8 numbered tiles and one empty space. The goal is to reach a target configuration by sliding tiles into the empty space.

State Representation

We represent each configuration as a vector of 9 integers (row-major order). The empty tile's position is tracked separately for efficient move generation. A map tracks visited configurations to avoid cycles.

Move Generation

From the empty tile's position (x, y), we consider four directions. When moving to a new position, we swap the corresponding elements in the vector representation:

• Up: index - 3
• Down: index + 3
• Left: index - 1
• Right: index + 1

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>

struct PuzzleState {
    std::vector<int> board;
    int emptyRow, emptyCol;
    int moves;
};

PuzzleState startState, goalState, currentState;
std::map<std::vector<int>, bool> visited;
int moveX[4] = {-1, 1, 0, 0};
int moveY[4] = {0, 0, -1, 1};

bool isGoalReached(const PuzzleState& s) {
    return s.board == goalState.board;
}

int solvePuzzle() {
    std::queue<PuzzleState> q;
    q.push(startState);
    visited[startState.board] = true;
    
    while (!q.empty()) {
        currentState = q.front();
        q.pop();
        
        if (isGoalReached(currentState)) {
            return currentState.moves;
        }
        
        for (int i = 0; i < 4; ++i) {
            int newRow = currentState.emptyRow + moveX[i];
            int newCol = currentState.emptyCol + moveY[i];
            
            if (newRow < 0 || newRow > 2 || newCol < 0 || newCol > 2) continue;
            
            PuzzleState next = currentState;
            int oldIndex = 3 * currentState.emptyRow + currentState.emptyCol;
            int newIndex = 3 * newRow + newCol;
            
            std::swap(next.board[oldIndex], next.board[newIndex]);
            next.emptyRow = newRow;
            next.emptyCol = newCol;
            
            if (!visited[next.board]) {
                visited[next.board] = true;
                next.moves = currentState.moves + 1;
                q.push(next);
            }
        }
    }
    return -1;
}

Problem 4: Magic Board Transformation

This puzzle involves an 8-digit circular board that can be transformed through three distinct operations. The goal is to reach a target configuration from the initial ordered state.

Operation Definitions

• Operasion A: Reverse the entire sequence
• Operation B: Rotate the middle segment rightward
• Operation C: Rotate the central four elements clockwise

Solution Approach

Similar to the 8-puzzle, we use BFS over the state space of board configurations. Each state stores the current sequence, operation history, and step count. The output must wrap operasion sequences at 60 characters per line.

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>

struct BoardState {
    std::vector<int> sequence;
    std::string operations;
    int steps;
};

BoardState initialBoard, targetBoard, currentBoard;
std::map<std::vector<int>, bool> explored;

bool sequencesMatch(const BoardState& a, const BoardState& b) {
    return a.sequence == b.sequence;
}

void solveMagicBoard() {
    std::queue<BoardState> q;
    q.push(initialBoard);
    explored[initialBoard.sequence] = true;
    
    while (!q.empty()) {
        currentBoard = q.front();
        q.pop();
        
        if (sequencesMatch(currentBoard, targetBoard)) {
            std::cout << currentBoard.steps << std::endl;
            for (size_t i = 0; i < currentBoard.operations.length(); ++i) {
                std::cout << currentBoard.operations[i];
                if ((i + 1) % 60 == 0) std::cout << std::endl;
            }
            std::cout << std::endl;
            return;
        }
        
        // Operation A: Reverse sequence
        BoardState afterA = currentBoard;
        afterA.sequence = std::vector<int>(currentBoard.sequence.rbegin(), 
                                            currentBoard.sequence.rend());
        if (!explored[afterA.sequence]) {
            explored[afterA.sequence] = true;
            afterA.operations += "A";
            afterA.steps++;
            q.push(afterA);
        }
        
        // Operation B: Circular shift
        BoardState afterB;
        afterB.sequence.push_back(currentBoard.sequence[3]);
        for (int i = 0; i < 3; ++i) 
            afterB.sequence.push_back(currentBoard.sequence[i]);
        for (int i = 5; i < 8; ++i) 
            afterB.sequence.push_back(currentBoard.sequence[i]);
        afterB.sequence.push_back(currentBoard.sequence[4]);
        
        if (!explored[afterB.sequence]) {
            explored[afterB.sequence] = true;
            afterB.operations = currentBoard.operations + "B";
            afterB.steps = currentBoard.steps + 1;
            q.push(afterB);
        }
        
        // Operation C: Rotate center
        BoardState afterC;
        afterC.sequence = {
            currentBoard.sequence[0],
            currentBoard.sequence[6],
            currentBoard.sequence[1],
            currentBoard.sequence[3],
            currentBoard.sequence[4],
            currentBoard.sequence[2],
            currentBoard.sequence[5],
            currentBoard.sequence[7]
        };
        
        if (!explored[afterC.sequence]) {
            explored[afterC.sequence] = true;
            afterC.operations = currentBoard.operations + "C";
            afterC.steps = currentBoard.steps + 1;
            q.push(afterC);
        }
    }
}

Problem 5: Triple Reservoir Measurement

A variation of the water jug problem with three containers. Starting with a full first container, we must achieve a target volume in any container through pouring operations.

State Space

Each state tracks volumes in three containers (a, b, c). There are six possible pouring operations between container pairs. The BFS terminates when any container reaches the target volume.

#include <iostream>
#include <queue>
#include <cstring>

const int MAX_VOL = 105;

struct ReservoirState {
    int volA, volB, volC;
    int steps;
};

int capacityA, capacityB, capacityC, target;
bool visited[MAX_VOL][MAX_VOL][MAX_VOL];

int measureWater() {
    std::queue<ReservoirState> q;
    ReservoirState start = {capacityA, 0, 0, 0};
    q.push(start);
    visited[capacityA][0][0] = true;
    
    while (!q.empty()) {
        ReservoirState current = q.front();
        q.pop();
        
        if (current.volA == target || current.volB == target || current.volC == target) {
            return current.steps;
        }
        
        // Pour A -> B
        int transfer = std::min(current.volA, capacityB - current.volB);
        if (!visited[current.volA - transfer][current.volB + transfer][current.volC]) {
            visited[current.volA - transfer][current.volB + transfer][current.volC] = true;
            q.push({current.volA - transfer, current.volB + transfer, current.volC, current.steps + 1});
        }
        
        // Pour A -> C
        transfer = std::min(current.volA, capacityC - current.volC);
        if (!visited[current.volA - transfer][current.volB][current.volC + transfer]) {
            visited[current.volA - transfer][current.volB][current.volC + transfer] = true;
            q.push({current.volA - transfer, current.volB, current.volC + transfer, current.steps + 1});
        }
        
        // Pour B -> A
        transfer = std::min(current.volB, capacityA - current.volA);
        if (!visited[current.volA + transfer][current.volB - transfer][current.volC]) {
            visited[current.volA + transfer][current.volB - transfer][current.volC] = true;
            q.push({current.volA + transfer, current.volB - transfer, current.volC, current.steps + 1});
        }
        
        // Pour B -> C
        transfer = std::min(current.volB, capacityC - current.volC);
        if (!visited[current.volA][current.volB - transfer][current.volC + transfer]) {
            visited[current.volA][current.volB - transfer][current.volC + transfer] = true;
            q.push({current.volA, current.volB - transfer, current.volC + transfer, current.steps + 1});
        }
        
        // Pour C -> A
        transfer = std::min(current.volC, capacityA - current.volA);
        if (!visited[current.volA + transfer][current.volB][current.volC - transfer]) {
            visited[current.volA + transfer][current.volB][current.volC - transfer] = true;
            q.push({current.volA + transfer, current.volB, current.volC - transfer, current.steps + 1});
        }
        
        // Pour C -> B
        transfer = std::min(current.volC, capacityB - current.volB);
        if (!visited[current.volA][current.volB + transfer][current.volC - transfer]) {
            visited[current.volA][current.volB + transfer][current.volC - transfer] = true;
            q.push({current.volA, current.volB + transfer, current.volC - transfer, current.steps + 1});
        }
    }
    return -1;
}

Each problem demonstrates core BFS patterns: state representation, transition generation, cycle detection, and termination conditions. The key is identifying the minimal state representation that captures all relevant information for the search.