1815:画家问题 C

2018-02-05 10:39:12来源:oschina作者:BinksCN人点击

分享

描述


有一个正方形的墙,由N*N个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时, 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。



输入


第一行是一个整数n (1≤n ≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。


输出


一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。


样例输入


5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出


15

——————————————————————分割线————————————————————


源代码


#include
int puzzle[20][20];
int press[20][20];
int n;
int ans;
int p=1;
bool guess()
{
int i,j;
for(i=2;i<=n;i++)
for(j=1;j<=n;j++)
press[i][j]=(puzzle[i-1][j]+press[i-1][j-1]+press[i-1][j]+press[i-1][j+1]+press[i-2][j])%2;
for(j=1;j<=n;j++)
if(press[n][j]!=(puzzle[n][j]+press[n][j-1]+press[n][j+1]+press[n-1][j])%2)
return true;
return false;
}
void solve()
{
for(c=1;c<=n;c++)
press[1][c]=0;
while(guess())
{
if(p==5000)
break;
p++;
press[1][1]++;
c=1;
while(press[1][c]>1)
{
press[1][c]=0;
c++;
press[1][c]++;
}
}
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<=n;i++)
puzzle[i][0]=puzzle[i][n+1]=press[i][0]=press[i][n+1]=0;
for(j=0;j<=n+1;j++)
puzzle[0][j]=puzzle[n][j]=press[0][j]=press[n][j]=0;
char c[20];
int a=1;
for(i=1;i<=n;i++)
{
scanf("%s",&c);
for(j=0;j<=n-1;j++)
{
if(c[j]=='w')
{
puzzle[i][j+1]=1;
a=0;
}
else
puzzle[i][j+1]=0;
}
}
if(a==0)
solve();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(press[i][j]==1)
ans++;
if(p==5000)
printf("inf/n");
else
printf("%d/n",ans);
return 0;
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台