Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <sstream>
- #include <algorithm>
- #include <fstream>
- #include <list>
- #include <unordered_map>
- #include <map>
- #include <istream>
- #include <sstream>
- #include <stack>
- #include <ctime>
- #include <stdio.h>
- #include <set>
- #include <cmath>
- #include <bitset>
- #include <iostream>
- #include <iomanip>
- #include <queue>
- #include <string>
- #define endl "\n"
- /*#define all(x) x.begin(),x.end()
- #define rr return 0
- #define xx first
- #define yy second
- #define pii pair<int,int>
- #define lcm(a,b) a*b/gcd(a,b)*/
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- signed main(){
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t;
- int r, c, h, v;
- cin >> t;
- int pp = 1;
- vector<vector<char>> a;
- vector<int> rows;
- vector<int> cols;
- while(t){
- cin >> r >> c >> h >> v;
- a.resize(r);
- rows.resize(r);
- cols.resize(c);
- string s;
- int ch = 0;
- for(int i = 0;i < r;i++){
- a[i].resize(c);
- cin >> s;
- for(int j = 0;j < c;j++){
- a[i][j] = s[j];
- if(a[i][j] == '@'){
- ch++;
- }
- }
- }
- int num = (h + 1) * (v + 1);
- if(ch == 0){
- cout << "Case #" << pp << ": ";
- pp++;
- cout << "POSSIBLE" << endl;
- continue;
- }
- int numc, numr;
- numc = ch / (v + 1);
- numr = ch / (h + 1);
- bool ok = true;
- if(ch % num != 0){
- ok = 0;
- }
- int inone = ch / num;
- for(int i = 0;i < r;i++){
- int u = 0;
- for(int j = 0;j < c;j++){
- if(a[i][j] == '@'){
- u++;
- }
- }
- rows[i] = u;
- }
- for(int i = 0;i < c;i++){
- int u = 0;
- for(int j = 0;j < r;j++){
- if(a[j][i] == '@'){
- u++;
- }
- }
- cols[i] = u;
- }
- int tmp = 0;
- int cs = 0;
- vector<int> colR;
- for(int i = 0;i < c;i++){
- tmp += cols[i];
- if(tmp > numc){
- ok = 0;
- }else if(tmp == numc){
- tmp = 0;
- cs++;
- if((i + 1) >= 0 && (i + 1) < c)
- colR.push_back(i + 1);
- }else if(i == c-1 && tmp < numc){
- ok = 0;
- }
- }
- colR.push_back(c);
- int rs = 0;
- int prevRaz = 0;
- tmp = 0;
- for(int i = 0;i < r;i++){
- tmp += rows[i];
- if(tmp > numr){
- ok = 0;
- }else if(tmp == numr){
- int ch1 = 0;
- int prev = 0;
- for(int j : colR){
- ch1 = 0;
- for(int z = prevRaz;z <= i;z++){
- for(int k = prev;k < j;k++){
- if(a[z][k] == '@'){
- ch1++;
- }
- }
- }
- prev = j;
- if(ch1 != inone){
- ok = 0;
- break;
- }
- }
- if(!ok){
- break;
- }
- tmp = 0;
- rs++;
- prevRaz = i + 1;
- }else if(i == r-1 && tmp < numr){
- ok = 0;
- }
- }
- if(cs != (v + 1) && rs != (h + 1)){
- ok = 0;
- }
- cout << "Case #" << pp << ": ";
- if(ok)
- cout << "POSSIBLE" << endl;
- else
- cout << "IMPOSSIBLE" << endl;
- --t;
- pp++;
- colR.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement