main.cpp (2105B)
1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <map> 5 #include <time.h> 6 7 using namespace std; 8 9 #define MAXN 200 10 11 int R, C, H, S; 12 char pizz[MAXN][MAXN]; // row, col 13 14 vector<int> size; 15 vector<vector<int> > G; 16 vector<int> r1; 17 vector<int> c1; 18 vector<int> r2; 19 vector<int> c2; 20 vector<int> ham; 21 22 int main(int argc, char **argv) { 23 scanf("%d%d%d%d", &R, &C, &H, &S); 24 25 for (int i = 0; i < R; i++) 26 scanf("%s", pizz[i]); 27 28 for (int r = 0; r < R; r++) 29 for (int c = 0; c < C; c++) 30 for (int w = 1; w <= S; w++) 31 for (int h = 1; w * h <= S; h++) { 32 if (c + w > C || r + h > R) 33 continue; // out of bounds 34 // count 35 int nham = 0; 36 for (int dr = 0; dr < h; dr++) 37 for (int dc = 0; dc < w; dc++) 38 nham += (pizz[r + dr][c + dc] == 'H' ? 1 : 0); 39 if (nham < H) 40 continue; // not enough ham 41 vector<int> nv; 42 G.push_back(nv); 43 ham.push_back(nham); 44 r1.push_back(r); 45 r2.push_back(r + h); 46 c1.push_back(c); 47 c2.push_back(c + w); 48 size.push_back(h * w); 49 } 50 51 // compute adj 52 for (unsigned int i = 0; i < G.size(); i++) { 53 G[i].push_back(i); 54 for (unsigned int j = i+1; j < G.size(); j++) { 55 if (r2[i] <= r1[j] || r1[i] >= r2[j] 56 || c2[i] <= c1[j] || c1[i] >= c2[j]) 57 continue; // not overlap 58 if (r2[j] <= r1[i] || r1[j] >= r2[i] 59 || c2[j] <= c1[i] || c1[j] >= c2[i]) 60 continue; // not overlap 61 // if (r1[i] == 0 && c1[i] == 0 && r2[i] == 1 && c2[i] == 8) { 62 // if (r1[j] == 0 && c1[j] == 0 && r2[j] == 1 && c2[j] == 9) { 63 // printf("YESSS %d %d\n", i, j); 64 // } 65 // } 66 G[i].push_back(j); 67 G[j].push_back(i); 68 } 69 } 70 71 printf("%d\n", (int) G.size()); 72 for (unsigned i = 0; i < G.size(); i++) { 73 printf("%d %d %d %d %d %d\n", size[i], r1[i], c1[i], r2[i], c2[i], ham[i]); 74 printf("%d\n", (int) G[i].size()); 75 for (unsigned j = 0; j < G[i].size(); j++) { 76 printf("%d\n", G[i][j]); 77 } 78 } 79 80 return 0; 81 } 82