queue / stack / deque：一头动还是两头动

// STL 专题 · queue —— BFS 的骨架就是这五句
//
//   ① 起点 push 进去        ② while (!q.empty())     ③ front 取出排头
//   ④ pop 让排头走人        ⑤ 邻居 push 进去
//
// ⚠ ③④ 是**两句**，而且顺序不能反：pop() 只负责让人走，它不给任何值。
// ⚠ 「来过没有」要另记一张表（这里用 dist == -1）—— 队列本身不帮你去重。

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<string> g(n);
  for (string &row : g) cin >> row;

  vector<vector<int>> dist(n, vector<int>(m, -1));   // -1 = 还没来过
  queue<pair<int, int>> q;
  dist[0][0] = 0;
  q.push({0, 0});

  const int dr[4] = {-1, 1, 0, 0};
  const int dc[4] = {0, 0, -1, 1};
  string order, line;
  int seen = 0;

  while (!q.empty()) {
    auto [r, c] = q.front();     // ★ 先看排头是谁
    q.pop();                     // ★ 再让他走人
    seen++;

    line += "(" + to_string(r) + "," + to_string(c) + ") ";
    if (line.size() > 50) { order += line + "\n"; line.clear(); }   // 每行不超过 50 列

    for (int k = 0; k < 4; k++) {
      int nr = r + dr[k], nc = c + dc[k];
      if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
      if (g[nr][nc] == '#') continue;
      if (dist[nr][nc] != -1) continue;              // ★ 来过就不再进队
      dist[nr][nc] = dist[r][c] + 1;
      q.push({nr, nc});
    }
  }
  if (!line.empty()) order += line;

  cout << "访问顺序（每次从队头取出的点）：\n" << order;
  cout << "\n到右下角最少走 " << dist[n - 1][m - 1] << " 步\n";
  cout << "一共进队出队 " << seen << " 个点，最后队列"
       << (q.empty() ? "空了" : "没空") << "\n";
  return 0;
}

// STL 专题 · deque —— 滑动窗口的最小值 / 最大值
//
// ★ 窗口从左往右挪：**新来的从队尾进，过期的从队头走** —— 两头各管一头，
//   这就是 deque 存在的理由（queue 只能动一头）。
//
// ★ 队列里存的是**下标**，不是值：
//     过期判据  d.front() <= i - k     （队头下标滑出窗口了）
//     保单调    比新来的小的队尾元素，后面再也轮不到它当最大 → 弹掉
//     打印      a[d.front()] 就是这个窗口的最大值
//
// ⚠ 方向写反不会编译报错，只会算出别的数 —— 见陷阱 ③。

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int &x : a) cin >> x;

  deque<int> d;                     // 存下标
  cout << "每个窗口的最大值：\n";
  for (int i = 0; i < n; i++) {
    while (!d.empty() && d.front() <= i - k) d.pop_front();   // ★ 过期的从队头走
    while (!d.empty() && a[d.back()] < a[i]) d.pop_back();    // 队尾比它小的，永远轮不到了
    d.push_back(i);                                           // ★ 新来的从队尾进

    if (i >= k - 1) {
      cout << "窗口 [" << (i - k + 1) << ", " << i << "]：";
      for (int j = i - k + 1; j <= i; j++) cout << a[j] << (j == i ? "" : " ");
      cout << "  ->  最大 " << a[d.front()] << "\n";
    }
  }
  cout << "\n走完之后队列里还剩 " << d.size() << " 个候选下标（队头就是全局最大值的下标）\n";
  return 0;
}