Mountain Walking
Kkyn
c_cpp
a year ago
2.3 kB
7
Indexable
#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; }
Editor is loading...
Leave a Comment