51nod1448(yy)

题目链接: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1448

题意: 中文题诶~ 不过要仔细看题, 原来颜色是被覆盖而非变成原来相反的颜色~

思路: 首先找到一个 k * k 的纯色矩阵 s1, 不需要管这个纯色矩阵是不是白色, 因为如果不是白色的话用白色印章将其覆盖一次即可. 然后再取 s1 中任意一点为左上角顶点, 引出一个 k * k 的矩阵 s2, 若 s2 中除了与 s1 公共部分外是纯色的, 那么显然可以将 s2 也覆盖成白色的. 接着从 s2 中任取一点为左上角顶点, 再引出一个 k * k 的矩阵 s3, 若其除了与前面的 s1, s2 公共部分外为纯色, 显然也是可以将 s3 覆盖成白色的...后面的依次类推即可.

最后再检查一遍是否还存在没被标记的 B, 若存在则输出 Impossible, 反之输出 Possible.

代码:

 #include <iostream>

 #include <string.h>

 using namespace std;

 const int MAXN = ;

 int vis[MAXN][MAXN];

 string s[MAXN];

 int main(void){

     int t;

     cin >> t;

     while(t--){

         int n, k;

         memset(vis, , sizeof(vis));

         cin >> n >> k;

         for(int i = ; i < n; i++){

             cin >> s[i];

         }

         bool flag = true;

         while(flag){

             flag = false;

             for(int i = ; i + k < n + ; i++){

                 for(int j = ; j + k < n + ; j++){

                     int cnt1 = , cnt2 = , cnt = ;

                     for(int l = ; l < k; l++){

                         for(int h = ; h < k; h++){

                             int x = i + l;

                             int y = j + h;

                             if(vis[x][y]) continue;

                             cnt = ;

                             if(s[x][y] == 'B') cnt1++;

                             else cnt2++;

                         }

                     }

                     if(cnt && (cnt1 ==  || cnt2 == )){

                         flag = true;

                         for(int l = ; l < k; l++){

                             for(int h = ; h < k; h++){

                                 int x = i + l;

                                 int y = j + h;

                                 vis[x][y] = ;

                             }

                         }

                     }

                 }

             }

         }

         flag = true;

         for(int i = ; i < n; i++){

             for(int j = ; j < n; j++){

                 if(!vis[i][j] && s[i][j] == 'B') flag = false;

             }

         }

         if(flag) cout << "Possible" << endl;

         else cout << "Impossible" << endl;

     }

     return ;

 }

巴特西

51nod1448(yy)

最新文章

热门文章