Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一个搜索题就过,发个贴,庆祝一下......

Posted by zhanghua at 2007-05-13 22:45:39 on Problem 1315
#include<stdio.h>
#include<math.h>
int chess[4][4];
int best;
int count;
void inicial()
{
	best=0;
	count=0;
}
int isok(int x,int n,int y)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		if(chess[x][i]==-1)
		{
			if(abs(y-i)==1){return 0;}
			else if(abs(y-i)==2)
			{
				if(chess[x][(y+i)/2]==0){return 0;}
			}
			else if(abs(y-i)==3)
			{
				if(chess[x][1]==0&&chess[x][2]==0)
				{
					return 0;
				}
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(chess[i][y]==-1)
		{
			if(abs(x-i)==1){return 0;}
			else if(abs(x-i)==2)
			{
				if(chess[(x+i)/2][y]==0){return 0;}
			}
			else if(abs(x-i)==3)
			{
				if(chess[1][y]==0&&chess[2][y]==0){return 0;}
			}
		}
	}
	return 1;
}
void recover(int n)
{
	int i,j;
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	{
		if(chess[i][j]==-1){chess[i][j]=0;}
	}
}
void search(int x,int n)
{
	int i,j;
	if(x>=n)
	{
		if(count>best)
		{
			best=count;
		}
	}
	else
	{
		for(i=0;i<n;i++)
		{


			if(isok(x,n,i)&&chess[x][i]==0)
			{
				count++;
				chess[x][i]=-1;
				search(x,n);
				count--;
				chess[x][i]=0;
			}

		}
		search(x+1,n);
	}
}
main()
{
	int n,i,j;
	char c[5],f;
	while(scanf("%d",&n)==1)
	{
		if(n==0)break;
		inicial();
		getchar();
		for(i=0;i<n;i++)
		{

			gets(c);
			for(j=0;j<n;j++)
			{
				f=c[j];
				if(f=='.')
				{
					chess[i][j]=0;
				}
				else if(f=='X')
				{
					chess[i][j]=1;
				}

			}
		}
		search(0,n);
		printf("%d\n",best);

       }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator