fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //#define int long long
  5. #define yes cout << "YES\n"
  6. #define no cout << "NO\n"
  7. #define el "\n"
  8. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. #define fix(x) cout << fixed << setprecision(x)
  10. #define all(v) v.begin(), v.end()
  11. int n,m,k;
  12. vector<vector<char>>arr;
  13. vector<vector<vector<int>>>pre;
  14. bool valid(int mid)
  15. {
  16.        for(int i=1;i<=n;i++)
  17.        {
  18.         for(int j=1;j<=m;j++)
  19.         {
  20.             int count=0;
  21.             for(int kk=0;kk<=25;kk++)
  22.             {
  23.             if(i+mid-1<=n&&j+mid-1<=m)
  24.             {
  25.                 int is =pre[kk][i+mid-1][j+mid-1]-pre[kk][i-1][j]-pre[kk][i][j-1]+pre[kk][i-1][j-1];
  26.                 if(is)
  27.                 {
  28.                     count++;
  29.                 }
  30.             }
  31.             }
  32.             if(count>=k)
  33.             return true;
  34.         }
  35.        }
  36.        return false;
  37. }
  38. pair<int,int> returnxy(int mid)
  39. {
  40.        for(int i=1;i<=n;i++)
  41.        {
  42.         for(int j=1;j<=m;j++)
  43.         {
  44.             int count=0;
  45.             for(int kk=0;kk<=25;kk++)
  46.             {
  47.             if(i+mid-1<=n&&j+mid-1<=m)
  48.             {
  49.             int is =pre[kk][i+mid-1][j+mid-1]-pre[kk][i-1][j]-pre[kk][i][j-1]+pre[kk][i-1][j-1];
  50.             if(is)
  51.             {
  52.                 count++;
  53.             }
  54.             }
  55.             }
  56.             if(count>=k)
  57.             {
  58.                 return {i,j};
  59.             }
  60.         }
  61.        }
  62.        return {-1,-1};
  63. }
  64. int32_t main()
  65. {
  66.     Arwa
  67.     int t=1;
  68.     //cin>>t;
  69.     while(t--)
  70.     { 
  71.        cin>>n>>m>>k;
  72.        arr.resize(n+1,vector<char>(m+1));
  73.        pre.resize(26,vector<vector<int>>(n+1,vector<int>(m+1,0)));
  74.        for(int i=1;i<=n;i++)
  75.        {
  76.         for(int j=1;j<=m;j++)
  77.          cin>>arr[i][j];
  78.        }
  79.        for(int i=1;i<=n;i++)
  80.        {
  81.         for(int j=1;j<=m;j++)
  82.         {
  83.             int ch =int(arr[i][j])-65;
  84.             pre[ch][i][j]++;
  85.         }
  86.        }
  87.        for(int kk=0;kk<=25;kk++)
  88.        {
  89.        for(int i=1;i<=n;i++)
  90.        {
  91.         for(int j=1;j<=m;j++)
  92.         {
  93.             pre[kk][i][j]=pre[kk][i][j]+pre[kk][i-1][j]+pre[kk][i][j-1]-pre[kk][i-1][j-1];
  94.         }
  95.        }
  96.  
  97.        }
  98.        int l=1,r=min(n,m),ans=-1,x=-1,y=-1;
  99.        while(l<=r)
  100.        {
  101.         int mid=(l+r)/2;
  102.         if(valid(mid))
  103.         {
  104.         ans=mid;
  105.         x=returnxy(mid).first;
  106.         y=returnxy(mid).second;
  107.         r=mid-1;
  108.         }
  109.         else
  110.         l=mid+1;
  111.        }
  112.        if(ans==-1)
  113.        cout<<ans<<el;
  114.        else 
  115.        {
  116.         cout<<ans<<el;
  117.         cout<<x<<' '<<y;
  118.        }
  119.     }
  120.         return 0;
  121. }
  122.  
  123.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/AbdU6B
language:
C++ (gcc 8.3)
created:
1 day 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!