Advertisement
MiinaMagdy

10946 - You want what filled?

Mar 13th, 2023
833
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define all(x) x.begin(), x.end()
  7. #define sz(x) int(x.size())
  8. #define endl '\n'
  9.  
  10. int n, m;
  11. int P;
  12.  
  13. void solve() {
  14.     cout << "Problem " << ++P << ":\n";
  15.     vector<pair<char, int>> ans;
  16.     vector<vector<char>> grid(n, vector<char>(m));
  17.     for (int i = 0; i < n; i++) {
  18.         for (int j = 0; j < m; j++) {
  19.             cin >> grid[i][j];
  20.         }
  21.     }
  22.     vector<vector<bool>> vis(n, vector<bool>(m));
  23.     auto valid = [&](int i, int j) {
  24.         return 0 <= i && i < n && 0 <= j && j < m && !vis[i][j];
  25.     };
  26.     function<int(int , int )> dfs = [&](int i, int j) {
  27.         int ans = 1;
  28.         int di = 0, dj = -1;
  29.         for (int _ = 0; _ < 4; _++) {
  30.             int ni = di + i, nj = dj + j;
  31.             if (valid(ni, nj) && grid[i][j] == grid[ni][nj]) {
  32.                 vis[ni][nj] = true;
  33.                 ans += dfs(ni, nj);
  34.             }
  35.             swap(di, dj);
  36.             if (_ == 1) dj = 1;
  37.         }
  38.         return ans;
  39.     };
  40.     for (int i = 0; i < n; i++) {
  41.         for (int j = 0; j < m; j++) {
  42.             if (isalpha(grid[i][j]) && !vis[i][j]) {
  43.                 vis[i][j] = true;
  44.                 ans.emplace_back(grid[i][j], dfs(i, j));
  45.             }
  46.         }
  47.     }
  48.     sort(all(ans), [](const pair<char, int>& a, const pair<char, int>& b) {
  49.         if (a.second == b.second) return a.first < b.first;
  50.         return a.second > b.second;
  51.     });
  52.     for (pair<char, int>& a : ans) cout << a.first << " " << a.second << endl;
  53. }
  54.  
  55. int main() {
  56.     cin.tie(0), cin.sync_with_stdio(0);
  57.     while (cin >> n >> m, n && m)
  58.         solve();
  59. }
  60.  
Tags: C++ UVA
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement