Mountain Walking

#include <iostream>

using namespace std;

const int N = 300;
const int NQ = 10000000;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

class Queue {
private:
    int front, rear, arr[NQ];
public:
    void init() {
        front = rear = -1;
    }
    bool isEmpty() {
        return front == rear;
    }
    void push(int data) {
        rear++;
        arr[rear % NQ] = data;
    }
    int pop() {
        if (!isEmpty()) {
            front++;
            return arr[front % NQ];
        }
        return -1;
    }
};

int n, a[N][N], visited[N][N];
Queue qx, qy;

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
}

bool bfs(int minDiff, int maxDiff) {
    if (a[0][0] < minDiff || a[0][0] > maxDiff) return false;
    
    qx.init();
    qy.init();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    qx.push(0);
    qy.push(0);
    visited[0][0] = true;
    
    while (!qx.isEmpty()) {
        int px = qx.pop();
        int py = qy.pop();
        
        if (px == n - 1 && py == n - 1) return true;
        
        for (int i = 0; i < 4; i++) {
            int newx = px + dx[i];
            int newy = py + dy[i];
            
            if (newx >= 0 && newx < n && newy >= 0 && newy < n && !visited[newx][newy] && a[newx][newy] >= minDiff && a[newx][newy] <= maxDiff) {
                qx.push(newx);
                qy.push(newy);
                visited[newx][newy] = true;
            }
        }
    }
    return false;
}

void solve(int tc) {
    int left = 0, right = 110;
    int result = 1e9;
    while (left <= right) {
        int mid = (right + left) / 2;
        bool found = false;
        for (int i = 0; i + mid <= 110; i++) {
            if (bfs(i, i + mid)) {
                found = true;
                break;
            }
            
        }
        if (found) {
            result = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    cout << "Case #" << tc << endl;
    cout << result << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    int t;
    cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        input();
        solve(tc);
    }
    return 0;
}