Greedily take the smallest character in both strings. What's the exception to this?

We can't take the smallest character in both strings when we've already took $$$k$$$ elements from that string. Denote $$$A$$$ as the number of characters we've took from string $$$a$$$ in the last moves and denote $$$B$$$ the same for $$$b$$$. If $$$A=k$$$, then we have to take the smallest character in string $$$b$$$ instead of possibly $$$a$$$. If $$$B=k$$$, then we have to take the smallest charater in string $$$a$$$ instead of possibly $$$b$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n,m,k; cin>>n>>m>>k;
        string a,b,c; cin>>a>>b;
        sort(a.begin(),a.end(),greater<char>());
        sort(b.begin(),b.end(),greater<char>());
 
        int ak=0,bk=0;
        while (!a.empty() && !b.empty())
        {
            bool gde=b.back()<a.back();
            if (gde && bk==k) gde=0;
            if (!gde && ak==k) gde=1;
 
            if (gde) c.push_back(b.back()),bk++,ak=0,b.pop_back();
            else c.push_back(a.back()),ak++,bk=0,a.pop_back();
        }
 
        cout<<c<<"\n";
    }
}

There are not a lot of useful black squares.

Consider this algorithm: iterate over all squares in the matrix and find the most distant black square.

Let's find out how to do that efficiently. In fact, only 4 (not necessarily distinct) squares will be useful: one square which minimizes $$$i-j$$$, one square which maximizes $$$i-j$$$, one square which minimizes $$$i+j$$$ and one square which maximizes $$$i+j$$$, where $$$(i,j)$$$ denotes the black cell's coordinates. In other words, we would like to find the most distant "border".

Let's look at the example above. The cell we choose to recolour to yellow creates four regions as shown. The most distant border will be fully contained inside one region, hence we should find distance from our yellow cell to any cell on that border, and that is the maximum possible distance.

#include <bits/stdc++.h>
 
using namespace std;
 
char tab[1003][1003];
pair<int,int> a={-1,-1},b={-1,-1},c={-1,-1},d={-1,-1};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        a={-1,-1},b={-1,-1},c={-1,-1},d={-1,-1};
        
        int n,m; cin>>n>>m;
        for (int i=0;i<n;i++) cin>>tab[i];
 
        vector<pair<int,int>> interesting;
 
        for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (tab[i][j]=='B')
        {
            if (a.first==-1 || i+j>a.first+a.second) a={i,j};
            if (b.first==-1 || i+j<b.first+b.second) b={i,j};
            if (c.first==-1 || i-j>c.first-c.second) c={i,j};
            if (d.first==-1 || i-j<d.first-d.second) d={i,j};
        }
 
        interesting.push_back(a);
        interesting.push_back(b);
        interesting.push_back(c);
        interesting.push_back(d);
 
        int ans=1e9; pair<int,int> opt;
        for (int i=0;i<n;i++) for (int j=0;j<m;j++)
        {
            int dist=0;
            for (auto it : interesting) dist=max(dist,abs(i-it.first)+abs(j-it.second));
            if (dist<ans) ans=dist,opt={i,j};
        }
 
        cout<<opt.first+1<<" "<<opt.second+1<<"\n";
    }
}