Advertisement
YEZAELP

PROG-1166: สวนดอกไม้

Jan 18th, 2022
649
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using pi = pair <int, int>;
  5. const int N = 30 + 10, M = 30 + 10;
  6. char ar[N][M];
  7. bool vs[N][M];
  8. int di[] = {0, 0, 1, -1};
  9. int dj[] = {1, -1, 0, 0};
  10. int n, m;
  11.  
  12. bool pst(int i, int j){
  13.     return 1 <= i and i <= n and 1 <= j and j <= m;
  14. }
  15.  
  16. bool check(int i, int j){
  17.     return ar[i][j] != '#' and
  18.            ar[i][j + 1] != '#' and
  19.            ar[i][j - 1] != '#' and
  20.            ar[i + 1][j] != '#' and
  21.            ar[i - 1][j] != '#';
  22. }
  23.  
  24. int bfs(int si, int sj, int cnt = 0){
  25.     queue <pi> q;
  26.     q.push({si, sj});
  27.     while(!q.empty()){
  28.         int ui = q.front().first;
  29.         int uj = q.front().second;
  30.         q.pop();
  31.         if(vs[ui][uj]) continue;
  32.         vs[ui][uj] = true;
  33.         cnt ++;
  34.         for(int d=0;d<4;d++){
  35.             int vi = ui + di[d];
  36.             int vj = uj + dj[d];
  37.             if(pst(vi, vj) and !vs[vi][vj] and check(vi, vj))
  38.                 q.push({vi, vj});
  39.         }
  40.     }
  41.     return cnt;
  42. }
  43.  
  44. int main(){
  45.  
  46.     scanf("%d %d", &n, &m);
  47.  
  48.     for(int i=1;i<=n;i++){
  49.         for(int j=1;j<=m;j++){
  50.             scanf(" %c", &ar[i][j]);
  51.         }
  52.     }
  53.  
  54.     int mx = 0;
  55.     for(int i=1;i<=n;i++){
  56.         for(int j=1;j<=m;j++){
  57.             if(!vs[i][j] and check(i, j))
  58.                 mx = max(mx, bfs(i, j));
  59.         }
  60.     }
  61.  
  62.     printf("%d", mx);
  63.  
  64.     return 0;
  65. }
  66.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement