題目：

注意，這題不是把一塊區(qū)域的黑翻成白、白翻成黑。

是把一塊區(qū)域全部翻成白或者翻成黑。

初始為全白，看能否翻出題中的情況。

我們假設(shè)翻轉(zhuǎn)若干次能得到圖中的形狀，那么我們找出最后一次的翻轉(zhuǎn)，即全W或者全B，讓這一塊區(qū)域置為隨機(jī)。（隨機(jī)可以看做B或者W中的一個(gè)）

直到把所有的這樣的翻轉(zhuǎn)全部找出來，置為隨機(jī)。

看最后是否有一定是B的點(diǎn)，如果有就說明無法翻轉(zhuǎn)到圖中的形狀，否則可以翻轉(zhuǎn)。

代碼：

#include <iostream> #include <algorithm> #include <map> #include <vector> #include <set> #include <math.h> #include <queue> #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <string> using namespace std; typedef long long ll; #define INF 2147483647int t,n,k; char a[25][25];//判斷以（x，y）為左上角的區(qū)域是否為同色，且不全為隨機(jī)。 bool isSame(int x,int y){bool flagB = false,flagW = false;for(int i = x;i <= x+k-1; i++){for(int j = y;j <= y+k-1; j++){if(a[i][j] == 'B'){flagB = true;}else if(a[i][j] == 'W'){flagW = true;}if(flagB && flagW){return false;}}}if(!flagB && !flagW) return false;return true; }//以（x，y）為左上角的區(qū)域置為隨機(jī) void makeRandom(int x,int y){for(int i = x;i <= x+k-1; i++){for(int j = y;j <= y+k-1; j++){a[i][j] = 'R';}} }int main(){cin >> t;while(t--){cin >> n >> k;for(int i = 1;i <= n; i++)for(int j = 1;j <= n; j++)cin >> a[i][j];while(true){bool update = false;for(int i = n-k+1;i >= 1; i--){for(int j = n-k+1;j >= 1; j--){ // cout << i << " " << j <<endl;if(isSame(i,j)){makeRandom(i,j);update = true;}}}if(!update) break; }bool flag = true;for(int i = 1;i <= n; i++){for(int j = 1;j <= n; j++){if(a[i][j] == 'B'){flag = false; }} }if(flag){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的51nod 1448 二染色问题 （逆向考虑）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。