Submission #792705

#	Time	Username	Problem	Language	Result	Execution time	Memory
792705		WLZ	Maze (JOI23_ho_t3)	C++17	27 / 100	2158 ms	1625504 KiB

Main

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

#ifdef DEBUG
#include "templates/debug.h"
#else
#define debug(...) 0
#endif

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) x.size()

using ll = long long;
using ull = unsigned ll;
using lll = __int128_t;
using ulll = __uint128_t;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
template<typename T> using mx_pq = priority_queue<T>;
template<typename T> using mn_pq = priority_queue<T, vector<T>, greater<T>>;

template<typename T> void cmax(T &a, const T &b) { a = max(a, b); }
template<typename T> void cmin(T &a, const T &b) { a = min(a, b); }

const int INF = 0x3f3f3f3f;
const ll LINF = (ll) 1e18;
const double DINF = 1.0 / 0.0;
const double pi = acos(-1);
const double EPS = 1e-9;

void solve(int current_case);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  //cin >> t;
  for (int q = 1; q <= t; q++) solve(q);
  return 0;
}

const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int r, c, n;
int sr, sc, gr, gc;
vector<string> grid;
vector<vii> g;

bool in_grid(int i, int j) {
  return i >= 0 && i < r && j >= 0 && j < c;
}

int idx(int i, int j) {
  return i * c + j;
}

void solve(int current_case) {
  cin >> r >> c >> n;
  cin >> sr >> sc; sr--; sc--;
  cin >> gr >> gc; gr--; gc--;
  grid.resize(r);
  rep(i, 0, r) cin >> grid[i];
  g.resize(3 * r * c);
  rep(i, 0, r) {
    rep(j, 0, c) {
      rep(k, 0, 4) {
        int ni = i + dx[k], nj = j + dy[k];
        if (in_grid(ni, nj) && grid[ni][nj] == '.') g[idx(i, j)].eb(idx(ni, nj), 0);
      }
      rep(ni, i, i + n) rep(nj, j, j + n) if (in_grid(ni, nj)) g[idx(i, j) + r * c].eb(idx(ni, nj), 0);
      rep(k, 0, n) {
        int ni = i - 1, nj = j + k;
        if (in_grid(ni, nj)) g[idx(ni, nj)].eb(idx(i, j) + r * c, 1);
        ni = i + n;
        if (in_grid(ni, nj)) g[idx(ni, nj)].eb(idx(i, j) + r * c, 1);
        ni = i + k, nj = j - 1;
        if (in_grid(ni, nj)) g[idx(ni, nj)].eb(idx(i, j) + r * c, 1);
        nj = j + n;
        if (in_grid(ni, nj)) g[idx(ni, nj)].eb(idx(i, j) + r * c, 1);
      }
    }
  }
  debug(idx(5, 3));
  debug(idx(2, 0));
  vi dist(3 * r * c, INF); dist[idx(sr, sc)] = 0;
  deque<ii> pq; pq.push_back({idx(sr, sc), 0});
  while (!pq.empty()) {
    int u = pq.back().first, d = pq.back().second;
    //debug(u, d);
    pq.pop_back();
    if (d > dist[u]) continue;
    for (auto &v : g[u]) {
      if (d + v.second >= dist[v.first]) continue;
      dist[v.first] = d + v.second;
      if (v.second == 0) pq.push_back({v.first, dist[v.first]});
      else pq.push_front({v.first, dist[v.first]});
    }
  }
  debug(dist);
  rep(i, 0, r) rep(j, 0, c) if (max(abs(i - gr), abs(j - gc)) < n) cmin(dist[idx(gr, gc)], dist[idx(i, j)] + 1);
  cout << dist[idx(gr, gc)] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void solve(int)':
Main.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
Main.cpp:90:3: note: in expansion of macro 'debug'
   90 |   debug(idx(5, 3));
      |   ^~~~~
Main.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
Main.cpp:91:3: note: in expansion of macro 'debug'
   91 |   debug(idx(2, 0));
      |   ^~~~~
Main.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
Main.cpp:106:3: note: in expansion of macro 'debug'
  106 |   debug(dist);
      |   ^~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6