제출 #1269410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269410		flashmt	Maze (JOI23_ho_t3)	C++20	100 / 100	778 ms	199884 KiB

Main

#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int DX[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int oo = 27081993;

int r, c;
string a[2525];

int isValid(int x, int y)
{
  return 0 <= x && x < r && 0 <= y && y < c;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, sx, sy, tx, ty;
  cin >> r >> c >> n;
  cin >> sx >> sy >> tx >> ty;
  sx--; sy--; tx--; ty--;
  for (int i = 0; i < r; i++)
    cin >> a[i];

  vector<vector<int>> dist(r, vector<int>(c, oo));
  vector<vector<int>> dist2(r, vector<int>(c, oo));
  vector<vector<int>> dir(r, vector<int>(c, -1));
  vector<vector<int>> step(r, vector<int>(c));
  dist[sx][sy] = 0;
  vector<pair<int, int>> q = {{sx, sy}};
  for (int curDist = 0; !empty(q); curDist++)
  {
    for (int i = 0; i < size(q); i++)
    {
      auto [x, y] = q[i];
      dist2[x][y] = step[x][y] = 0;
      for (int j = 0; j < 4; j++)
      {
        int xx = x + DX[j], yy = y + DY[j];
        if (isValid(xx, yy) && dist[xx][yy] == oo && a[xx][yy] == '.')
        {
          dist[xx][yy] = curDist;
          q.push_back({xx, yy});
        }
      }
    }

    vector<pair<int, int>> nextQ;
    for (int i = 0; i < size(q); i++)
    {
      auto [x, y] = q[i];
      if (dist[x][y] == oo)
      {
        dist[x][y] = curDist + 1;
        nextQ.push_back({x, y});
      }
      if (dist2[x][y] == n)
        continue;

      for (int j = 0; j < 8; j++)
      {
        int xx = x + DX[j], yy = y + DY[j];
        if (isValid(xx, yy) && dist2[xx][yy] == oo)
        {
          if (j == dir[x][y]) step[xx][yy] = step[x][y] + 1;
          else step[xx][yy] = 1;

          // exclude 4 corners
          if (dist2[x][y] == n - 1 && step[xx][yy] == n && j >= 4)
            continue;

          q.push_back({xx, yy});
          dist2[xx][yy] = dist2[x][y] + 1;
          dir[xx][yy] = j;
        }
      }
    }
    swap(q, nextQ);
  }

  cout << dist[tx][ty] << endl;
}

• 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