The UVA589 problem requires finding the optimal path to push a box to a target location. The optimization criteria have two levels: primarily minimizing the number of pushes, and secondarily minimizing the total number of moves when push counts are equal.

Key Problem Constraints

• The primary objective is to minimize push operations, not walking distance.
• If multiple solutions have the same push count, choose the one with the fewest total moves.
• Output requires a blank line after each test case.
• The output format includes "Maze #" followed by the test case number.

Algorithm Design

A single BFS combined with a priority queue (min-heap) can solve this problem efficiently. The key insight is structuring the priority comparison to handle both optimization criteria.

Define a state structure to track all necessary information:

struct GameState {
    int playerRow, playerCol;
    int crateRow, crateCol;
    string path;
    int pushCount;
    int totalSteps;
    
    bool operator>(const GameState& other) const {
        if (pushCount != other.pushCount) {
            return pushCount > other.pushCount;
        }
        return totalSteps > other.totalSteps;
    }
};

A 4-dimensional boolean array tracks visited states: visited[playerRow][playerCol][crateRow][crateCol]. This ensures each unique configuration of player and box positions is processed once.

Implementation Details

The validation function handles movement logic:

bool canMove(GameState& state, int direction) {
    int newRow = state.playerRow + dirX[direction];
    int newCol = state.playerCol + dirY[direction];
    
    if (newRow < 1 || newRow > rows || newCol < 1 || newCol > cols) {
        return false;
    }
    if (grid[newRow][newCol] == '#') {
        return false;
    }
    if (visited[newRow][newCol][state.crateRow][state.crateCol]) {
        return false;
    }
    
    if (newRow == state.crateRow && newCol == state.crateCol) {
        int crateNewRow = state.crateRow + dirX[direction];
        int crateNewCol = state.crateCol + dirY[direction];
        
        if (crateNewRow < 1 || crateNewRow > rows || 
            crateNewCol < 1 || crateNewCol > cols) {
            return false;
        }
        if (grid[crateNewRow][crateNewCol] == '#') {
            return false;
        }
        
        state.crateRow = crateNewRow;
        state.crateCol = crateNewCol;
        state.pushCount++;
        state.path += pushCmd[direction];
    } else {
        state.path += moveCmd[direction];
    }
    
    state.totalSteps++;
    state.playerRow = newRow;
    state.playerCol = newCol;
    visited[newRow][newCol][state.crateRow][state.crateCol] = true;
    return true;
}

The BFS traversal uses the priority queue:

void solve(GameState initial, int caseNum) {
    priority_queue pq;
    pq.push(initial);
    visited[initial.playerRow][initial.playerCol]
           [initial.crateRow][initial.crateCol] = true;
    
    while (!pq.empty()) {
        GameState current = pq.top();
        pq.pop();
        
        for (int d = 0; d < 4; d++) {
            GameState next = current;
            if (canMove(next, d)) {
                if (grid[next.crateRow][next.crateCol] == 'T') {
                    cout << "Maze #" << caseNum << endl;
                    cout << next.path << endl;
                    found = true;
                    return;
                }
                pq.push(next);
            }
        }
    }
}

Complete Solution

#include 
using namespace std;

const int MAXN = 25;
int rows, cols;
char grid[MAXN][MAXN];
bool visited[MAXN][MAXN][MAXN][MAXN];
bool found;

int dirX[4] = {0, 0, 1, -1};
int dirY[4] = {1, -1, 0, 0};
char pushCmd[4] = {'E', 'W', 'S', 'N'};
char moveCmd[4] = {'e', 'w', 's', 'n'};

struct GameState {
    int playerRow, playerCol;
    int crateRow, crateCol;
    string path;
    int pushCount;
    int totalSteps;
    
    bool operator>(const GameState& o) const {
        if (pushCount != o.pushCount) return pushCount > o.pushCount;
        return totalSteps > o.totalSteps;
    }
};

bool canMove(GameState& st, int dir) {
    int nRow = st.playerRow + dirX[dir];
    int nCol = st.playerCol + dirY[dir];
    
    if (nRow < 1 || nRow > rows || nCol < 1 || nCol > cols) return false;
    if (grid[nRow][nCol] == '#') return false;
    if (visited[nRow][nCol][st.crateRow][st.crateCol]) return false;
    
    if (nRow == st.crateRow && nCol == st.crateCol) {
        int cRow = st.crateRow + dirX[dir];
        int cCol = st.crateCol + dirY[dir];
        if (cRow < 1 || cRow > rows || cCol < 1 || cCol > cols) return false;
        if (grid[cRow][cCol] == '#') return false;
        st.crateRow = cRow;
        st.crateCol = cCol;
        st.pushCount++;
        st.path += pushCmd[dir];
    } else {
        st.path += moveCmd[dir];
    }
    st.totalSteps++;
    st.playerRow = nRow;
    st.playerCol = nCol;
    visited[nRow][nCol][st.crateRow][st.crateCol] = true;
    return true;
}

void bfs(GameState init, int num) {
    priority_queue pq;
    pq.push(init);
    visited[init.playerRow][init.playerCol][init.crateRow][init.crateCol] = true;
    
    while (!pq.empty()) {
        GameState cur = pq.top();
        pq.pop();
        for (int d = 0; d < 4; d++) {
            GameState nxt = cur;
            if (canMove(nxt, d)) {
                if (grid[nxt.crateRow][nxt.crateCol] == 'T') {
                    cout << "Maze #" << num << endl << nxt.path << endl;
                    found = false;
                    return;
                }
                pq.push(nxt);
            }
        }
    }
}

int main() {
    int caseNum = 1;
    while (cin >> rows >> cols && rows && cols) {
        found = true;
        memset(visited, 0, sizeof(visited));
        GameState init;
        init.path = "";
        init.pushCount = 0;
        init.totalSteps = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                cin >> grid[i][j];
                if (grid[i][j] == 'S') { init.playerRow = i; init.playerCol = j; }
                if (grid[i][j] == 'B') { init.crateRow = i; init.crateCol = j; }
            }
        }
        
        bfs(init, caseNum);
        if (found) {
            cout << "Maze #" << caseNum << endl << "Impossible." << endl;
        }
        cout << endl;
        caseNum++;
    }
    return 0;
}

The solution leverages Dijkstra-like expansion with the priority queue, ensuring states with fewer pushes are processed first. When push counts tie, states with fewer total steps take priority, naturally producing the optimal solution.