STANAANDREY

hackathon: "the xiaolin"

Jan 24th, 2022 (edited)
407
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. constexpr char BARRIER = '#';
  4. int n, m;
  5. vector<vector<char>> board;
  6. vector<vector<int>> dis;
  7. constexpr int NR_DIRS = 4, dirI[] = {0, 0, 1, -1}, dirJ[] = {1, -1, 0, 0};
  8. unordered_map<int, int> fr;
  9.  
  10. void read() {
  11.     cin >> n >> m;
  12.     board.resize(n + 3, vector<char>(m + 3, BARRIER));
  13.     dis.resize(n + 3, vector<int>(m + 3, INT_MAX));
  14.     for (int i = 1; i <= n; i++) {
  15.         for (int j = 1; j <= m; j++) {
  16.             cin >> board[i][j];
  17.         }
  18.     }
  19. }
  20.  
  21. void lee() {
  22.     queue<pair<int, int>> q;
  23.     q.emplace(1, 1);
  24.     dis[1][1] = 0;
  25.     while (!q.empty()) {
  26.         const auto &[i, j] = q.front();
  27.         q.pop();
  28.         for (int dir = 0; dir < NR_DIRS; dir++) {
  29.             int newI = i + dirI[dir];
  30.             int newJ = j + dirJ[dir];
  31.             if (board[newI][newJ] != BARRIER && dis[newI][newJ] > dis[i][j] + 1) {
  32.                 dis[newI][newJ] = dis[i][j] + 1;
  33.                 q.emplace(newI, newJ);
  34.             }
  35.         }
  36.     }
  37. }
  38.  
  39. void cnt() {
  40.     for (int i = 1; i <= n; i++) {
  41.         for (int j = 1; j <= m; j++) {
  42.             if ((i == 1 && j == 1) || (i == n && j == m) || board[i][j] == BARRIER) {
  43.                 continue;
  44.             }
  45.             fr[dis[i][j]]++;
  46.         }
  47.     }
  48. }
  49.  
  50. void getAns() {
  51.     int ans = INT_MAX;
  52.     if (dis[n][m] == INT_MAX) {
  53.         ans = 0;
  54.     } else {
  55.         for (const auto &it : fr) {
  56.             ans = min(ans, it.second);
  57.         }
  58.     }
  59.     cout << ans << endl;
  60. }
  61.  
  62. signed main() {
  63.     read();
  64.     lee();
  65.     cnt();
  66.     getAns();
  67.     return 0;
  68. }
  69.  
RAW Paste Data Copied