fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define MOD 1000000007
  4. #define E "\n"
  5.  
  6. using namespace std;
  7.  
  8. int m,n,s;
  9. vector<int>neighRow={0,1,0,-1};
  10. vector<int>neighCol={1,0,-1,0};
  11.  
  12. int bfs2(int i,int j,vector<vector<int>>&vis){
  13.     queue<pair<int,int>>q;
  14.     vector<vector<int>>vis2(m+2,vector<int>(n+2,-1));
  15.     int count=1;
  16.     q.push({i,j});
  17.     vis2[i][j]=1;
  18.     while(q.size()){
  19.         auto it=q.front();
  20.         int x=it.first,y=it.second;
  21.         q.pop();
  22.         for(int i=0;i<4;i++){
  23.             int row=x+neighRow[i],col=y+neighCol[i];
  24.             if(row>=0 && col>=0 && row<m+2 && col<n+2 && vis[row][col]==-1 && vis2[row][col]==-1){
  25.                 count++;
  26.                 vis[row][col]=1,vis2[row][col]=1;;
  27.                 q.push({row,col});
  28.             }
  29.         }
  30.     }
  31.     return count;
  32. }
  33.  
  34. int main() {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(NULL);
  37.  
  38. #ifndef ONLINE_JUDGE
  39.     freopen("warm.txt", "r", stdin);
  40.     freopen("output.txt", "w", stdout);
  41. #endif
  42.  
  43.     int t,c=1;
  44.     cin >> t;
  45.     while (t--) {
  46.         cin>>m>>n>>s;
  47.  
  48.         vector<vector<char>>v(m+2,vector<char>(n+2,'#'));
  49.         vector<vector<int>>vis(m+2,vector<int>(n+2,-1));
  50.         for(int i=1;i<=m;i++){
  51.             for(int j=1;j<=n;j++){
  52.                 cin>>v[i][j];
  53.             }
  54.         }
  55.         queue<vector<int>>q;
  56.         for(int i=0;i<m+2;i++){
  57.             for(int j=0;j<n+2;j++){
  58.                 if(v[i][j]=='#'){
  59.                     q.push({i,j,0});
  60.                     vis[i][j]=1;    
  61.                 }
  62.             }
  63.         }
  64.         while(q.size()){
  65.             auto it=q.front();
  66.             q.pop();
  67.             int x=it[0],y=it[1],count=it[2];
  68.             if(count>=s)
  69.                 continue;
  70.             for(int i=0;i<4;i++){
  71.                 int row=x+neighRow[i],col=y+neighCol[i];
  72.                 if(row>=0 && col>=0 && row<m+2 && col<n+2 && vis[row][col]==-1){
  73.                     vis[row][col]=1;
  74.                     q.push({row,col,count+1});
  75.                 }
  76.             }
  77.         }
  78.         int maxi=0;
  79.         for(int i=1;i<=m;i++){
  80.             for(int j=1;j<=n;j++){
  81.                 if(vis[i][j]==-1){
  82.                     maxi=max(maxi,bfs2(i,j,vis));
  83.                 }
  84.             }
  85.         }
  86.         cout<<"Case #"<<c<<": "<<maxi<<endl;
  87.         c++;
  88.     }
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zje7aH
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!