http://cxsjsxmooc.openjudge.cn/test/Y/
代碼
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
int map[20][20];//草稿
int copy[20][20];//原始記錄
int line[20];//第一行
char col[20];//輸入緩沖區(qū)
int n;
int min;
int count;
void draw(int x,int y){//畫畫并且增加次數(shù)
map[x][y]=!map[x][y];
map[x-1][y]=!map[x-1][y];
map[x+1][y]=!map[x+1][y];
map[x][y-1]=!map[x][y-1];
map[x][y+1]=!map[x][y+1];
count++;
}
bool guess(){
//從第二行開始 判斷每個點上邊的點是否為黃色 如果不是黃色 則涂該點
for(int i=2; i<=n; i++)
for(int j=1; j<=n; j++)
if(map[i-1][j] == 0)
draw(i,j);
//判斷最后一行是否都為黃色 如果是則記錄次數(shù) 否則提交失敗
for(int k=1; k<=n; k++)
if(map[n][k] != 1)
return false;
if(count < min)
min = count;
return true;
}
void getLine(int k){
//二進制枚舉第一行
int j=n;
while(j>0){
line[j]=k%2;
k/=2;
j--;
}
}
int main(){
int w;
cin>>w;
while(w--){
cin>>n;
min=n*n+1;
for (int i = 1; i <=n; ++i) {
scanf("%s",col);
//一行一行掃描
for (int j = 1; j <=n ; ++j) {
if(col[j-1]=='w'){
copy[i][j]=0;
}
else{
copy[i][j]=1;
}
}
}
//開始枚舉
for (int k = 0; k <pow(2,n) ; ++k) {
count=0;
memcpy(map,copy, sizeof(copy));
getLine(k);
//枚舉第一行
for (int i = 1; i <=n ; ++i) {
if(line[i]==1){
draw(1,i);
}
}
guess();
}
if(min!=n*n+1){
cout<<min<<endl;
}
else{
cout<<"inf"<<endl;
}
}
return 0;
}
