Submission #1352086

#TimeUsernameProblemLanguageResultExecution timeMemory
1352086edoSirologija (COI24_sirologija)C++20
100 / 100
145 ms20296 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<vector<char>> mat(n, vector<char>(m));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> mat[i][j];
    }
  }

  int ans = 1;
  vector<vector<char>> right(n, vector<char>(m, 0));
  vector<vector<char>> left(n, vector<char>(m, 0));
  left[0][0] = (mat[0][0] != '#');

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (mat[i][j] == '#')
        continue;
      if (i && left[i - 1][j])
        left[i][j] = 1;
      if (j && left[i][j - 1])
        left[i][j] = 1;
    }
  }

  right[n - 1][m - 1] = (mat[n - 1][m - 1] != '#');

  for (int i = n - 1; ~i; --i) {
    for (int j = m - 1; ~j; --j) {
      if (mat[i][j] == '#')
        continue;
      if (i + 1 < n && right[i + 1][j])
        right[i][j] = 1;
      if (j + 1 < m && right[i][j + 1])
        right[i][j] = 1;
    }
  }

  vector<vector<char>> good(n, vector<char>(m));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      good[i][j] = left[i][j] && right[i][j];
    }
  }

  if (!good[0][0]) {
    cout << 0;
    return 0;
  }

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

  vector<vector<char>> visited(n, vector<char>(m, 0));

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (good[i][j] || visited[i][j])
        continue;
      queue<pair<int, int>> qu;
      qu.push({i, j});
      visited[i][j] = 1;
      int t = (!i || !j || i == n - 1 || j == m - 1);
      while (qu.size()) {
        auto [x, y] = qu.front();
        qu.pop();
        for (int d = 0; d < 8; ++d) {
          int nx = x + dx[d], ny = y + dy[d];
          if (min(nx, ny) < 0 || nx >= n || ny >= m || visited[nx][ny] ||
              good[nx][ny])
            continue;
          visited[nx][ny] = 1;
          if (!nx || !ny || nx == n - 1 || ny == m - 1)
            t = 1;
          qu.push({nx, ny});
        }
      }
      ans += !t;
    }
  }

  cout << ans;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...