c.cpp

堡垒问题

#include<stdio.h>
#define MAX 100
int max;
void main()
{
	void Search(char map[4][4],int m,int all,int cw,int n);
	char map[4][4],n,result[100];
	int i,j,m=0;
	scanf("%d",&n);
	getchar();
	while(n)
	{
		max=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
				scanf("%c",&map[i][j]);
			getchar();
		}
		Search(map,0,n*n,0,n);
		printf("%d\n",max);
		m++;
		scanf("%d",&n);
		getchar();
	}
}
/*int Complace(int m,char map[4][4],int n)
{
	int x,y,i,key,key_1=0,key_2=0;
	x=m/n;
	y=m%n;
	if(map[x][y]!='.') return 0;
	key=0;
	key_1=1;
	for(i=y-1;i>=0;i--)
	{
		if(map[x][i]=='X')
			key=1;
		else if(map[x][i]=='A'&&key==0)
		{
			key_1=0;
			break;
		}
	}
	if(key_1)
	{
		key=0;
		key_2=1;
		for(i=x-1;i>=0;i--)
		{
			if(map[i][y]=='X')
				key=1;
			else if(map[i][y]=='A'&&key==0)
			{
				key_2=0;
				break;
			}
		}
	}
	if(key_1&&key_2)
		return 1;
	return 0;
}*/
int Complace(int m,char map[4][4],int n)
{
	int x,y,i,key_1,key_2,j;
	x=m/n;
	y=m%n;
	if(map[x][y]!='.') return 0;
	for(i=y-1;i>=0;i--)
		if(map[x][i]=='A')
			break;
	if(i<0) key_1=1;
	else
	{
		for(j=i+1;j<y;j++)
			if(map[x][j]=='X')
				break;
		if(j==y) key_1=0;
		else key_1=1;
	}
	for(i=x-1;i>=0;i--)
		if(map[i][y]=='A')
			break;
	if(i<0) key_2=1;
	else
	{
		for(j=i+1;j<x;j++)
			if(map[j][y]=='X')
				break;
		if(j==x) key_2=0;
		else key_2=1;
	}
	if(key_1==1&&key_2==1)
		return 1;
	return 0;
}

void Place(char map[4][4],int m,int n)
{
	int x,y;
	x=m/n;
	y=m%n;
	map[x][y]='A';
}
void Takeoff(char map[4][4],int m,int n)
{
	int x,y;
	x=m/n;
	y=m%n;
	map[x][y]='.';
}
void Search(char map[4][4],int m,int all,int cw,int n)
{
	if(m>=all)
	{
		if(cw>max)
			max=cw;
	}
	else
	{
		if(Complace(m,map,n))
		{
			cw++;
			Place(map,m,n);
			Search(map,m+1,all,cw,n);
			cw--;
			Takeoff(map,m,n);
		}
		Search(map,m+1,all,cw,n);
	}
}