1002.cpp

zju acm 1002 算法实现了1002要求

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int max;
int width;
int length=0;
int *matrix;
//FILE *fp=fopen("input.txt","rw");
int init(){
	max=0;
	length=width*width;
	matrix=new int[length];
	char p[128];
	for(int i=0;i<width;i++){
	scanf("%s",&p);
	for(int j=0;j<width;j++){
		if(p[j]=='X')
			matrix[i*width+j]=1;
		else
			matrix[i*width+j]=0;
	}
	}
	return 0;
}
bool isInArray(int a,int array[]){
	for(int i=0;i<length;i++){
	if(a==array[i])
	return true;
	}
	return false;
}

bool isCanIn(int a,int b[]){
	int index=0;
	int temp=0;
	int i=a/width;
	int j=a%width;
	for(index=j-1;index>=0;index--){
	temp=i*width+index;
	if(matrix[temp]==1)
		break;
	if(isInArray(temp,b))
		return false;
	}
	for(index=j+1;index<width;index++){
	temp=i*width+index;
	if(matrix[temp]==1)
		break;
	if(isInArray(temp,b))
		return false;
	}
	for(index=i-1;index>=0;index--){
	temp=index*width+j;
	if(matrix[temp]==1)
		break;
	if(isInArray(temp,b))
		return false;
	}
	for(index=i+1;index<width;index++){
	temp=index*width+j;
	if(matrix[temp]==1)
		break;
	if(isInArray(temp,b))
		return false;
	}
	return true;

}

int* findCanUse(int b[]){
	int *canUse=new int[length];
	memset(canUse,-1, length*sizeof(int));
	int index=0;
	for(int i=0;i<length;i++){
		if(matrix[i]==0){
			if(isInArray(i,b))
			continue;
			else{
				if(isCanIn(i,b)){
				canUse[index]=i;
				index++;
				}
			}
		}
	}
	return canUse;
}

int iterateAndFind(int inUse[],int tempMax,int canUse[]){
	if(canUse[0]==-1)
		return 0;
	for(int i=0;i<length;i++){	
		if(canUse[i]!=-1){
		int myTempMax=tempMax+1;
		if(myTempMax>max)
			max=myTempMax;
		inUse[tempMax]=canUse[i];
		iterateAndFind(inUse,myTempMax,findCanUse(inUse));
		}

	}

	return 0;
}

int main(){
	scanf("%d",&width);
	while(width!=0){
	init();
	int *inUse=new int[length];
	memset(inUse,-1, length*sizeof(int));
	int *canUse=findCanUse(inUse);
	iterateAndFind(inUse,0,canUse);
	printf("%d\n",max);
	scanf("%d",&width);
	}
	return 0;
}