1681.cpp

非常好的C++学习源码,里面包括各种算法的实现,二叉的的前中后序遍历等

#include<iostream>
using namespace std;
int n,k,i,j,l,paint[16][17],b[16][17],sum,t=0;
char a[16][17];

bool guess()
{
	int p,q;
	for (p=1;p<=k-1;p++)
		for (q=1;q<=k;q++)
			paint[p+1][q]=(b[p][q]+paint[p][q]+paint[p-1][q]+paint[p][q-1]+paint[p][q+1])%2;
	for (p=1;p<=k;p++)
		if (b[k][p]!=(paint[k][p]+paint[k-1][p]+paint[k][p+1]+paint[k][p-1])%2)
			return (false);
	return (true);
}

void f(int d)
{
	int w;
	for (w=0;w<=1;w++)
	{
		if (t==1)
			return;
		paint[1][d]=w;
		if (d==k)
		{
		    if (guess()==true)
			{
				t=1;
				return;
			}
		}
		if (d<k)
			f(d+1);
	}
}

int main()
{
	cin>>n;
	for (i=1;i<=n;i++)
	{
		t=0;
		sum=0;
		cin>>k;
		for (j=0;j<16;j++)
		{
			for (l=0;l<17;l++)
			{
				paint[j][l]=0;
				b[j][l]=0;
			}
		}
		for (j=1;j<=k;j++)
		{
			for (l=1;l<=k;l++)
			{
				cin>>a[j][l];
				if (a[j][l]=='y')
					b[j][l]=0;
				else 
					b[j][l]=1;
			}
		}
		f(1);
		if (t==0)
			cout<<"inf"<<endl;
		else
		{
			for (j=1;j<=k;j++)
				for (l=1;l<=k;l++)
					sum=sum+paint[j][l];
			cout<<sum<<endl;
		}
	}
	return 0;
}


/*
void press(int x,int y)
{
	step++;
	c[x][y]=1-c[x][y];
	if (x>0) c[x-1][y]=1-c[x-1][y];

}

void bbbbb()
{
	step=0;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			c[i][j]=cc[i][j];

	for (i=0;i<n;i++)
		if (a[i]==1) press(0,i);
	for (i=1;i<=n-1;i++)
		for (j=0;j<n;j++)
			if (c[i-1][j]==0) press(i,j);
	b=1;

	if ((b==1)&&(step>max)) max=step;
}

void dg(int d)
{
	int k;
	for (k=0;k<=1;k++)
	{
		a[d]=k;
		if (d==n-1) bbbbb();
		else dg(d+1);
	}
}

max=0;
dg(0);
*/