Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 100;
- int qsum[N + 10][N + 10];
- int row, col, rCut, cCut;
- int getsum(int x1, int y1, int x2, int y2){
- return qsum[x2][y2] - qsum[x1 - 1][y2] - qsum[x2][y1 - 1] + qsum[x1 - 1][y1 - 1];
- }
- vector<int> divided;
- bool divideC(int c, int cut, int sum){
- if(cut == 0){
- return true;
- }
- for(int i = c; i <= col - cut; ++i){
- if(c == 1){
- bool broken = false;
- for(int j = 0; j < (int)divided.size() - 1; ++j){
- if(j == 0){
- sum = getsum(divided[j] + 1, c, divided[j + 1], i);
- } else if(getsum(divided[j] + 1, c, divided[j + 1], i) != sum){
- broken = true;
- break;
- }
- }
- if(!broken && getsum(1, i + 1, row, col) == sum * cut * (rCut + 1) && divideC(i + 1, cut - 1, sum)){
- return true;
- }
- } else {
- bool broken = false;
- for(int j = 0; j < (int)divided.size() - 1; ++j){
- if(getsum(divided[j] + 1, c, divided[j + 1], i) != sum){
- broken = true;
- break;
- }
- }
- if(!broken && getsum(1, i + 1, row, col) == sum * cut * (rCut + 1) && divideC(i + 1, cut - 1, sum)){
- return true;
- }
- }
- }
- return false;
- }
- bool divideR(int r, int cut, int sum){
- if(cut == 0){
- divided.push_back(row);
- return divideC(1, cCut, -1);
- divided.pop_back();
- }
- for(int i = r; i <= row - cut; ++i){
- if(r == 1){
- divided.push_back(i);
- sum = getsum(r, 1, i, col);
- if(getsum(i + 1, 1, row, col) == sum * cut && divideR(i + 1, cut - 1, sum)){
- return true;
- }
- divided.pop_back();
- } else if(getsum(r, 1, i, col) == sum){
- divided.push_back(i);
- if(getsum(i + 1, 1, row, col) == sum * cut && divideR(i + 1, cut - 1, sum)){
- return true;
- }
- divided.pop_back();
- }
- }
- return false;
- }
- int main(){
- int Q;
- scanf("%d", &Q);
- for(int q = 1; q <= Q; ++q){
- cout << "Case #" << q << ": ";
- divided.assign(1, 0);
- scanf("%d%d%d%d", &row, &col, &rCut, &cCut);
- for(int i = 1; i <= row; ++i){
- for(int j = 1; j <= col; ++j){
- char c;
- scanf(" %c", &c);
- if(c == '@'){
- qsum[i][j] = 1;
- } else if(c == '.'){
- qsum[i][j] = 0;
- }
- qsum[i][j] += qsum[i - 1][j] + qsum[i][j - 1] - qsum[i - 1][j - 1];
- }
- }
- if(divideR(1, rCut, -1)){
- cout << "POSSIBLE\n";
- } else {
- cout << "IMPOSSIBLE\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement