Türkçe

Çözüm

Soruyu çözerken basit bir dynamic programming algoritması kullanacağız. Kareleri seçerken sağ alta doğru büyüyen en büyük kareyi bulacağız (bu şekilde yapıyoruz çünkü eğer onu içeren daha büyük bir kare varsa üstündeki veya solundaki karelerden birinde o sayıyı bulmuş oluruz)

1. Önce dikdörtgensel bölgenin dış kısmını hesaplıyoruz(en sağ sütun ve en alt satırdaki alanlar). Bunların hepsinin büyüklüğü 1 (siyahlar hariç onları kapsayan kare yok o yüzden 0)
2. Daha sonra her sütun için (veya satır dealer's choice) en alt noktadan başlayarak:
   • Eğer noktamız engelliyse(siyah) hepsi beyazlardan oluşan hiç bir kare oluşamayacağı için 0 olarak işaretliyoruz
   • Eğer noktamız engelsizse 1 sağındaki, 1 altındaki ve 1 sağ alt çaprazındaki daha önceden hesaplanmış 3 kareye bakıyoruz
     • altındaki ve sağ alt çaprazındaki karelerin minimumu aşağıya doğru kaç birim daha ilerleyebileceğini söylüyor.
     • sağındaki ve sağ alt çaprazındaki karelerin minimumu sağa doğru kaç birim daha ilerleyebileceğini söylüyor. Bu nedenlerden dolayı bu üç sayının minimumunun bir fazlası elimizdeki kareyi içerip sağ alta doğru büyüyen en büyük karenin kenar uzunluğunu veriyor yani: \(arr[i][j]=min(arr[i+1][j],arr[i][j+1],arr[i+1][j+1])+1\) bunu son kareye kadar hesaplarken bulduğumuz en yüksek sayı cevabımız oluyor.

Not: Daha iyi bir cevap bulduğunuz her an indexlerini kaydetmeyi unutmayın.

English

Solution

We will use a simple dynamic programming algorithm. When choosing the squares, we will find the biggest square that grows towards the bottom-right, because if there is a bigger square containing that one, we will find that number in one of the left or top squares.

1. First, we calculate the outer side of the rectangular area(cells in right-most column and bottom-most row). These all have size 1 (except the black ones, their size is 0 because there are no squares containing them.)
2. Next, for every column (or row, dealer's choice) starting from the lower-most point:
   • If our point is blocked (black) we mark it as 0 because there is no all-white square.
   • If our point is not blocked, we look at the previously calculated 3 points: right one, bottom one, and bottom-right one.
     • the minimum of bottom and bottom-right tells how many units we can move downwards.
     • the minimum of right and bottom-right tells us how many units we can move to the right. Thus, the minimum of these 3 numbers gives us the edge length of the biggest square that grows towards the bottom-right. Namely the biggest value we find while calculating \(arr[i][j]=min(arr[i+1][j],arr[i][j+1],arr[i+1][j+1])+1\) until the last square gives us the answer.

Warning: Don't forget to record the indices as soon as you find better answers.

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

struct ARR{
    bool iswhite;
    int num;
};

int main(){
    char temp;
    ll row,col;
    cin>>row>>col;

    ARR arr[row][col];
    for(int i=0;i<row;i++)for(int k=0;k<col;k++){
        cin>>temp;
        switch(temp){
            case 'W':arr[i][k].iswhite=true;break;
            case 'B':arr[i][k].iswhite=false;break;
        }
    }

    int res=0;
    int fx=0,fy=0;

    //-------------------------------------------------------------------
        // English: Assigning last column and row
        // Turkish: son satır ve sütunun atanması
    for(int i=0;i<row;i++){
        if(arr[i][col-1].iswhite){
            arr[i][col-1].num=1;
            res=1;
            fx=i;
            fy=col-1;
        }
        else arr[i][col-1].num=0;
    }
    for(int i=0;i<col;i++){
        if(arr[row-1][i].iswhite){
            arr[row-1][i].num=1;
            res=1;
            fx=row-1;
            fy=i;
        }
        else arr[row-1][i].num=0;
    }

    //-------------------------------------------------------------------
        // English: Calculating other cells from already calcualted result
        // Turkish: Geri kalan karelerin önceden hesaplanmış karelerden hesaplanması
    for(int i=row-2;i>-1;i--){
        for(int k=col-2;k>-1;k--){
            if(arr[i][k].iswhite){
                arr[i][k].num=min(min(arr[i+1][k].num,arr[i][k+1].num),arr[i+1][k+1].num)+1;
                if(arr[i][k].num>res){
                    res=arr[i][k].num;
                    fx=i;
                    fy=k;
                }
            }
            else {
                arr[i][k].num=0;
            }
        }
    }

    //-------------------------------------------------------------------

    cout<<fx<<' '<<fy<<' '<<fx+res-1<<' '<<fy+res-1<<endl;
}