JAM: Waffle Choppers

#include <bits/stdc++.h>

using namespace std;
const int N = 1e2;
int qs[N+10][N+10];
vector <int> Col;
int n, m;

bool check(int part, int block){
    int previ = 0, cnt = 0;
    for(int i=1;i<=n;i++){
        int prevj = 0;
        bool ch = true;
        for(auto j: Col){
            int sum = qs[i][j] - qs[i][prevj] - qs[previ][j] + qs[previ][prevj];
            if(sum != block){
                ch = false;
                break;
            }
            prevj = j;
        }
        if(!ch) continue;
        cnt += Col.size();
        previ = i;
    }
    return cnt == part;
}

bool f(){
    scanf("%d%d", &n, &m);
    int h, v;
    scanf("%d%d", &h, &v);
    h ++;
    v ++;
    int part = h * v;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char ch;
            scanf(" %c", &ch);
            qs[i][j] = qs[i-1][j] + qs[i][j-1] - qs[i-1][j-1] + (ch == '@');
        }
    }

    int block = qs[n][m] / part;

    int SumCol = block * h;
    int prevj = 0;
    for(int j=1;j<=m;j++){
        if(qs[n][j] - qs[n][prevj] == SumCol) {
            Col.push_back(j);
            prevj = j;
        }
    }

    if(qs[n][m] == 0) return true;
    return check(part, block);
}

int main(){

    int Q;
    scanf("%d", &Q);

    for(int q=1;q<=Q;q++){
        if(f()) printf("Case #%d: POSSIBLE", q);
        else printf("Case #%d: IMPOSSIBLE", q);
        printf("\n");
        if(!Col.empty()) Col.clear();
    }


    return 0;
}