#1160776 (C++17) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: tnakao0123
• 提出日時: 2026-04-20 13:49:57
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 321 ms / 2,000 ms
• コード長: 2,695 bytes
• コンパイル時間: 590 ms
• コンパイル使用メモリ: 79,584 KB
• 実行使用メモリ: 39,168 KB
• 最終ジャッジ日時: 2026-04-20 13:50:13
• 合計ジャッジ時間: 13,176 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 85

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3504.cc:  No.3504 Insert Maze - yukicoder
 */

#include<cstdio>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_H = 2000;
const int MAX_W = 2000;
const int MAX_HW = MAX_H * MAX_W;
const int INF = 1 << 29;
const int dxs[] = {1, 0, -1, 0}, dys[] = {0, -1, 0, 1};

/* typedef */

using qi = queue<int>;
using pii = pair<int,int>;
using dqpii = deque<pii>;

/* global variables */

char fs[MAX_HW + 4];
int ds0[MAX_HW], ds1[MAX_HW];

/* subroutines */

void bfs(int h, int w, int st, int ds[]) {
  int hw = h * w;
  fill(ds, ds + hw, INF);
  ds[st] = 0;
  qi q;
  q.push(st);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int uy = u / w, ux = u % w;
    int vd = ds[u] + 1;
    for (int di = 0; di < 4; di++) {
      int vy = uy + dys[di], vx = ux + dxs[di], v = vy * w + vx;
      if (vy >= 0 && vy < h && vx >= 0 && vx < w &&
	  fs[v] != '#' && ds[v] > vd)
	ds[v] = vd, q.push(v);
    }
  }
}

/* main */

int main() {
  int h, w;
  scanf("%d%d", &h, &w);
  for (int i = 0; i < h; i++) scanf("%s", fs + i * w);

  int hw = h * w;
  int st = 0, gl = hw - 1;

  int mind = h + w;
  bfs(h, w, st, ds0);
  bfs(h, w, gl, ds1);
  mind = min(mind, ds0[gl]);
  
  for (int y0 = 0, y1 = 1; y1 < h; y0++, y1++) {
    dqpii rq;
    for (int x1 = 0, u1 = y1 * w; x1 < w; x1++, u1++) {
      while (! rq.empty() && rq.back().first >= ds1[u1] + x1) rq.pop_back();
      rq.push_back({ds1[u1] + x1, x1});
    }

    int lmnd = INF;
    for (int x0 = 0, u0 = y0 * w; x0 < w; x0++, u0++) {
      while (! rq.empty() && rq.front().second < x0) {
	int x1 = rq.front().second; rq.pop_front();
	int d1 = ds1[y1 * w + x1] - x1;
	lmnd = min(lmnd, d1);
      }

      if (! rq.empty()) {
	int rd = ds0[u0] - x0 + rq.front().first + 2;
	mind = min(mind, rd);
      }
      if (lmnd < INF) {
	int ld = ds0[u0] + x0 + lmnd + 2;
	mind = min(mind, ld);
      }
    }
  }
  
  for (int x0 = 0, x1 = 1; x1 < w; x0++, x1++) {
    dqpii dq;
    for (int y1 = 0, u1 = x1; y1 < h; y1++, u1 += w) {
      while (! dq.empty() && dq.back().first >= ds1[u1] + y1) dq.pop_back();
      dq.push_back({ds1[u1] + y1, y1});
    }

    int umnd = INF;
    for (int y0 = 0, u0 = x0; y0 < h; y0++, u0 += w) {
      while (! dq.empty() && dq.front().second < y0) {
	int y1 = dq.front().second; dq.pop_front();
	int d1 = ds1[y1 * w + x1] - y1;
	umnd = min(umnd, d1);
      }

      if (! dq.empty()) {
	int dd = ds0[u0] - y0 + dq.front().first + 2;
	mind = min(mind, dd);
      }
      if (umnd < INF) {
	int ud = ds0[u0] + y0 + umnd + 2;
	mind = min(mind, ud);
      }
    }
  }
  
  printf("%d\n", mind);
  
  return 0;
}