有一个正方形的墙,由NN个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i,j)个位置的砖时, 位置(i−1,j)、 (i+1,j)、(i,j−1)、(i,j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。
输入格式:
第一行是一个整数n (1≤n ≤16),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。
输出格式:
一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
输入样例:
在这里给出一组输入。例如:
5
wwwww
wwwww
wwwww
wwwww
wwwww
输出样例:
在这里给出相应的输出。例如:
15
熄灯问题没什么好方法,只能一层一层推导。
AC代码:
#indpude<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" const ll N = 1e1+7 ,M = 1e5+7; ll n; ll color[N][N],dp[N][N]; ll pd(ll z){ for(ll i = 1 ; i < z ; i ++)//尝试涂色,当前点的颜色由初始画板和涂色区推出 for(ll j = 1 ; j <= z ; j ++) dp[i+1][j]=(color[i][j]+dp[i-1][j]+dp[i][j-1]+dp[i][j]+dp[i][j+1])%2; for(ll i = 1 ; i <= z ; i ++)//由最后一行判断当前涂色能否成功 if(color[z][i] != (dp[z-1][i]+dp[z][i-1]+dp[z][i]+dp[z][i+1])%2)return M; ll sum=0;//算涂色次数 for(ll i = 1 ; i <= z ; i ++) for(ll j = 1 ; j <= z ; j ++) if(dp[i][j])sum++; return sum; } ll found(ll x){ ll sum = M ,cnt = 0 ,y; while(dp[1][x+1] < 1){ cnt = pd(x); if(cnt < sum)sum=cnt; dp[1][1]++; y=1; while(dp[1][y] > 1){ dp[1][y]=0; y++; dp[1][y]++; } } return sum; } void solve(){ memset(dp,0,sizeof dp); memset(color,0,sizeof color); cin >> n; for(ll i = 1 ; i <= n ; i ++) for(ll j = 1 ; j <= n ; j ++){ char c;cin >> c; if(c == 'w')color[i][j]=1; } ll sum = found(n); sum == M ? cout << "inf" << endl : cout << sum << endl; return; } int main(){ ll t=1;//cin >> t; while(t --)solve(); return 0; }