SRM496 Div1 Easy

250

貪欲

view plainprint?

1. class ColoredStrokes {  
2. public:  
3.   int getLeast(vector <string> P)  
4.   {  
5.     int cnt = 0;  
6.   
7.     const int h = P.size(), w = P[0].size();  
8.     bool b[h][w];  
9.     bool r[h][w];  
10.   
11.     fill(&b[0][0], &b[h - 1][w], false);  
12.     fill(&r[0][0], &r[h - 1][w], false);  
13.   
14.     for (int i = 0; i < (int)P.size(); ++i) {  
15.       for (int j = 0; j < (int)P[i].size(); ++j) {  
16.         if (b[i][j]) continue;  
17.         if (P[i][j] == 'B' || P[i][j] == 'G') ; else continue;  
18.         ++cnt;  
19.         for (int k = i; k < (int)h; ++k) {  
20.           if (P[k][j] == 'B' || P[k][j] == 'G') ; else break;  
21.           b[k][j] = true;           
22.         }  
23.       }  
24.     }  
25.      
26.     for (int i = 0; i < (int)P.size(); ++i) {  
27.       for (int j = 0; j < (int)P[i].size(); ++j) {  
28.         if (r[i][j]) continue;  
29.         if (P[i][j] == 'R' || P[i][j] == 'G') ; else continue;  
30.         ++cnt;  
31.         for (int k = j; k < (int)w; ++k) {  
32.           if (P[i][k] == 'R' || P[i][k] == 'G') ; else break;  
33.           r[i][k] = true;           
34.         }  
35.       }  
36.     }  
37.   
38.     return cnt;  
39.   }  
40. };  

class ColoredStrokes {
public:
  int getLeast(vector <string> P)
  {
    int cnt = 0;

    const int h = P.size(), w = P[0].size();
    bool b[h][w];
    bool r[h][w];

    fill(&b[0][0], &b[h - 1][w], false);
    fill(&r[0][0], &r[h - 1][w], false);

    for (int i = 0; i < (int)P.size(); ++i) {
      for (int j = 0; j < (int)P[i].size(); ++j) {
        if (b[i][j]) continue;
        if (P[i][j] == 'B' || P[i][j] == 'G') ; else continue;
        ++cnt;
        for (int k = i; k < (int)h; ++k) {
          if (P[k][j] == 'B' || P[k][j] == 'G') ; else break;
          b[k][j] = true;         
        }
      }
    }
   
    for (int i = 0; i < (int)P.size(); ++i) {
      for (int j = 0; j < (int)P[i].size(); ++j) {
        if (r[i][j]) continue;
        if (P[i][j] == 'R' || P[i][j] == 'G') ; else continue;
        ++cnt;
        for (int k = j; k < (int)w; ++k) {
          if (P[i][k] == 'R' || P[i][k] == 'G') ; else break;
          r[i][k] = true;         
        }
      }
    }

    return cnt;
  }
};