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

I am crazy! help 如何不超时?

Posted by fxzy at 2006-01-05 07:39:36 on Problem 1185
#include<stdio.h>
int key[102][12];
char map[102][12];
int max=0;
int n,m;
int check(int i,int j)
 { if(map[i][j]=='P'&&key[i][j]==0)
	 {if(j>=1)
	   if(key[i][j-1]==1)
	     return 0;
	     
	   if(j>=2)
	   if(key[i][j-2]==1)
	     return 0;
	     
	   if(j+1<=m-1)
	   if(key[i][j+1]==1)
	     return 0;
	       
	   if(j+2<=m-1)
	   if(key[i][j+2]==1)
	     return 0;
	     
	   if(i>=1)
	   if(key[i-1][j]==1)
	     return 0;
	     
	  if(i>=2)
	   if(key[i-2][j]==1)
	     return 0;
	     
	  if(i+1<=n-1)
	   if(key[i+1][j]==1)
	     return 0;
	     
	    if(i+2<=n-1)
	   if(key[i+2][j]==1)
	     return 0; 
	     
	   return 1;   
	 }  
	else return 0; 
	 }
	 
void put(int k,int hang,int lie)
 {
	 
	 int i,j;
	 i=hang;
	 for(j=lie;j<=m-1;j++)
	  if(check(i,j))
	   {key[i][j]=1;put(k+1,i,j);key[i][j]=0;}
	   
	 for(i=hang+1;i<=n-1;i++)  
	  for(j=0;j<=m-1;j++)
	   if(check(i,j))
	     {key[i][j]=1;put(k+1,i,j);key[i][j]=0;}
	   
	    if(i>n-1&&j>m-1)
	      if(max<k)
	        {max=k;return;} 
	 }
	 	 
int main()
{  int i,j;
	scanf("%d%d",&n,&m);
	 for(i=0;i<=n-1;i++)
	    scanf("%s",map[i]);
	    
	 for(i=0;i<=n-1;i++)
	  for(j=0;j<=m-1;j++)
	   key[i][j]=0;       
	 put(0,0,0);
	 printf("%d\n",max);
	 getchar();
	 getchar();
	}

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