Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //https://codeforces.com/contest/1985/problem/H1
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <string>
- #include <cstdint>
- #include <iostream>
- #include <set>
- #include <numeric>
- #include <queue>
- #include <map>
- #include <iomanip>
- #include <sstream>
- #include <unordered_map>
- using namespace std;
- void Dfs(const vector<vector<char>>& field, vector<vector<bool>>& is_visited,
- vector<vector<int>>& types, int type, int i, int j, int& size)
- {
- is_visited[i][j] = true;
- ++size;
- types[i][j] = type;
- for (int di = -1; di <= 1; ++di) {
- for (int dj = -1; dj <= 1; ++dj) {
- if (di * di + dj * dj != 1) continue;
- int ni = i + di;
- int nj = j + dj;
- if (ni < 0 || field.size() <= ni || nj < 0 || field.front().size() <= nj) continue;
- if (is_visited[ni][nj]) continue;
- if (field[ni][nj] == '.') continue;
- Dfs(field, is_visited, types, type, ni, nj, size);
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int t;
- cin >> t;
- while (t--) {
- int rows_count, columns_count;
- cin >> rows_count >> columns_count;
- vector<vector<char>> field(rows_count, vector<char>(columns_count));
- for (auto& row : field) for (auto& elem : row) cin >> elem;
- vector<vector<bool>> is_visited(rows_count, vector<bool>(columns_count, false));
- vector<vector<int>> types(rows_count, vector<int>(columns_count, 0));
- vector<int> type_size = {0};
- int type = 1;
- for (int i = 0; i < field.size(); ++i) {
- for (int j = 0; j < field.front().size(); ++j) {
- if (field[i][j] == '.') continue;
- if (is_visited[i][j]) continue;
- int size = 0;
- Dfs(field, is_visited, types, type, i, j, size);
- type_size.push_back(size);
- ++type;
- }
- }
- int result = 0;
- vector<int> t(type_size.size(), -1);
- for (int i = 0; i < field.size(); ++i) {
- int cur_result = 0;
- for (int j = 0; j < field.front().size(); ++j) {
- if (field[i][j] != '.' && t[types[i][j]] != i) {
- cur_result += type_size[types[i][j]];
- t[types[i][j]] = i;
- }
- if (field[i][j] == '.') ++cur_result;
- for (int di = -1; di <= 1; ++di) {
- for (int dj = -1; dj <= 1; ++dj) {
- if (di * di + dj * dj != 1) continue;
- int ni = i + di;
- int nj = j + dj;
- if (ni < 0 || field.size() <= ni || nj < 0 || field.front().size() <= nj) continue;
- if (types[ni][nj] == 0) continue;
- if (t[types[ni][nj]] != i) {
- cur_result += type_size[types[ni][nj]];
- t[types[ni][nj]] = i;
- }
- }
- }
- }
- result = max(result, cur_result);
- }
- for (int& elem : t) elem = -1;
- for (int j = 0; j < field.front().size(); ++j) {
- int cur_result = 0;
- for (int i = 0; i < field.size(); ++i) {
- if (field[i][j] != '.' && t[types[i][j]] != j) {
- cur_result += type_size[types[i][j]];
- t[types[i][j]] = j;
- }
- if (field[i][j] == '.') ++cur_result;
- for (int di = -1; di <= 1; ++di) {
- for (int dj = -1; dj <= 1; ++dj) {
- if (di * di + dj * dj != 1) continue;
- int ni = i + di;
- int nj = j + dj;
- if (ni < 0 || field.size() <= ni || nj < 0 || field.front().size() <= nj) continue;
- if (types[ni][nj] == 0) continue;
- if (t[types[ni][nj]] != j) {
- cur_result += type_size[types[ni][nj]];
- t[types[ni][nj]] = j;
- }
- }
- }
- }
- result = max(result, cur_result);
- }
- cout << result << '\n';
- }
- return 0;
- }
- /*
- tes1
- 1
- 3 5
- .#.#.
- ..#..
- .#.#.
- 9
- test2
- 1
- 5 5
- #...#
- ....#
- #...#
- .....
- ...##
- 11
- test3
- 1
- 4 2
- ..
- #.
- #.
- .#
- 6
- */
Advertisement
Add Comment
Please, Sign In to add comment