1002.txt

浙江大学ａｃｍ试题答案之１００２

#include <iostream.h>

#define wall -1
#define house 2

int map[6][6];

int firenet(int n)
{	
	int k=0,i,j,p,q;
	char c;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			cin>>c;
			if(c=='.')
				map[i][j]=0;
			else
				map[i][j]=wall;
		}
	for(i=1;i<=n;i++)   map[i][n+1]=wall;
	for(j=1;j<=n;j++)   map[n+1][j]=wall;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if((map[i+1][j]==wall||map[i][j+1]==wall)&&map[i][j]==0)
			{
				map[i][j]=house;
				k++;
				q=j;
				while(map[i][q+1]!=wall)
				{
					q++;
					map[i][q]=wall;
				}
				p=i;
				while(map[p+1][j]!=wall)
				{
					p++;
					map[p][j]=wall;
				}
			}
		}
	return k;
}

int main()
{
	int n,i=0;
	cin>>n;
	while(n!=0)
	{
		cout<<firenet(n)<<endl;
		cin>>n;
	}
	return 0;
}












#include <stdio.h> 
char map[4][4]; 
int best,n; 

int CanPut(int row, int col) 
{ 
	int i; 
	for (i = row - 1; i >= 0; i--)
	{ 
		if (map[i][col] == 'O') return 0; 
		if (map[i][col] == 'X') break; 
	} 
	for (i = col - 1; i >= 0; i--) 
	{ 
		if (map[row][i] == 'O') return 0; 
		if (map[row][i] == 'X') break; 
	} 
	return 1; 
} 

void solve(int k,int tot) 
{ 
	int x,y; 
	if(k==n*n) 
	{ 
		if(tot>best) {best=tot;return;} 
	} 
	else
	{ 
		x=k/n;y=k%n; 
		if((map[x][y]=='.')&&(CanPut(x,y))) 
		{
			map[x][y]='O'; 
			solve(k+1,tot+1); 
			map[x][y]='.';
		} 
		solve(k+1,tot); 
	} 
} 
int main()
{ 
	int i,j; 
	scanf("%d",&n); 
	while(n>0)
	{ 
		for(i=0;i<n;i++) 
		for(j=0;j<n;j++) 
		scanf("%1s",&map[i][j]); /*输入单个字符并且忽略空白*/ 
		best=0; 
		solve(0,0); 
		printf("%d\n",best); 
		n=0; /*预防scanf失败，reset n*/ 
		scanf("%d",&n); 
	} 
	return 0; 
}