Submission #1105284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105284		vjudge1	Maze (JOI23_ho_t3)	C++17	100 / 100	1587 ms	288328 KiB

Main

#include <bits/stdc++.h>

	 

	// #define int int64_t

	 

	const int kMaxT = 6e6 + 5, kMaxN = 3e3 + 5;

	const int kD4[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

	const int kD8[][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

	 

	int n, m, k;

	int sx, sy, tx, ty;

	std::vector<int> G[kMaxT];

	std::string s[kMaxN];

	 

	void dijkstra() {

	  std::vector<std::vector<std::pair<int, int>>> dis(n + 1, std::vector<std::pair<int, int>>(m + 1));

	  std::vector<std::vector<bool>> vis(n + 1, std::vector<bool>(m + 1));

	  std::priority_queue<std::tuple<int, int, int, int>> q;

	  for (int i = 1; i <= n; ++i)

	    for (int j = 1; j <= m; ++j)

	      dis[i][j] = {1e9, 1e9};

	  dis[sx][sy] = {0, k - 1};

	  q.emplace(0, -(k - 1), sx, sy);

	  for (; !q.empty();) {

	    auto [d, w, x, y] = q.top();

	    q.pop();

	    if (vis[x][y]) continue;

	    vis[x][y] = 1;

	    for (auto [dx, dy] : kD4) {

	      int tx = x + dx, ty = y + dy;

	      if (tx < 1 || tx > n || ty < 1 || ty > m) continue;

	      if (s[tx][ty] == '.') {

	        std::pair<int, int> p = {dis[x][y].first, k - 1};

	        if (dis[tx][ty] > p) {

	          dis[tx][ty] = p;

	          q.emplace(-p.first, -p.second, tx, ty);

	        }

	      }

	      std::pair<int, int> p = {dis[x][y].first + 1, 0};

	      if (dis[tx][ty] > p) {

	        dis[tx][ty] = p;

	        q.emplace(-p.first, -p.second, tx, ty);

	      }

	    }

	    if (dis[x][y].second < k - 1) {

	      for (auto [dx, dy] : kD8) {

	        int tx = x + dx, ty = y + dy;

	        if (tx < 1 || tx > n || ty < 1 || ty > m) continue;

	        std::pair<int, int> p = {dis[x][y].first, dis[x][y].second + 1};

	        if (dis[tx][ty] > p) {

	          dis[tx][ty] = p;

	          q.emplace(-p.first, -p.second, tx, ty);

	        }

	      }

	    }

	  }

	  std::cout << dis[tx][ty].first << '\n';

	}

	 

	void dickdreamer() {

	  std::cin >> n >> m >> k >> sx >> sy >> tx >> ty;

	  for (int i = 1; i <= n; ++i) {

	    std::cin >> s[i];

	    s[i] = " " + s[i];

	  }

	  dijkstra();

	}

	 

	int32_t main() {

	#ifdef ORZXKR

	  freopen("in.txt", "r", stdin);

	  freopen("out.txt", "w", stdout);

	#endif

	  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

	  int T = 1;

	  // std::cin >> T;

	  while (T--) dickdreamer();

	  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";

	  return 0;

	}

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