Submission #900052

#	Time	Username	Problem	Language	Result	Execution time	Memory
900052		stefanneagu	Maze (JOI23_ho_t3)	C++17	8 / 100	597 ms	18012 KiB

Main

// subtask 1

// ca n-am idei

// cred ca o astfel de pb s-ar putea da la lot

#include <bits/stdc++.h>

using namespace std;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int main() {
  int n, m, k, si, sj, ei, ej;
  cin >> n >> m >> k >> si >> sj >> ei >> ej;
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  vector<vector<char>> mat(n + 1, vector<char>(m + 1));
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) {
      cin >> mat[i][j];
      dp[i][j] = 1e9;
    }
  }
  deque<pair<int, int>> dq;
  dq.push_back({si, sj});
  dp[si][sj] = 0;
  if(mat[si][sj] == '#') {
    dp[si][sj] ++;
  }
  while(!dq.empty()) {
    int i = dq.front().first, j = dq.front().second;
    dq.pop_front();
    for(int d = 0; d < 4; d ++) {
      int x = i + dx[d];
      int y = j + dy[d];
      if(x < 1 || y < 1 || x > n || y > m) {
        continue;
      }
      if(dp[x][y] > dp[i][j] + (mat[x][y] == '#')) {
        dp[x][y] = dp[i][j] + (mat[x][y] == '#');
        if(dq.empty() || dp[dq.front().first][dq.front().second] > dp[x][y]) {
          dq.push_front({x, y});
        } else {
          dq.push_back({x, y});
        }
      }
    }
  }
  cout << dp[ei][ej];
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 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