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

测试数据过了,但总是wrong answer,我用的是搜索,加了个可行性剪枝,请高手看一下,谢了

Posted by philipfry at 2007-09-09 12:32:41 on Problem 1185
#include <iostream>
using namespace std;
char a[200][40];
int b[200][40],c[200][40],ll,ww,pn=0;
int i,j,k,maxl=0,max=0,maxt=0,flag=0;
/////////////////////////////////


void row(int r,int l){
if(max+int((ll-l+1)*ww/3+2)>maxt){
	if (l==1){
	   if(r<=ww){
         if (b[l][r]==0){
	     c[l][r]=2;
		 max++;
		 row(r+3,l);
		 c[l][r]=0;
		 max--;
		 row(r+1,l);
		 }
         else
         row (r+1,l);
		 }
	   else
		   row(1,l+1);
	}
    else
		if (l<=ll){

		//for(k=1;k<=ww;k++)
		//	if(c[l][k]>0) 
		//		c[l][k]--;
		  if(r<=ww){
          if (b[l][r]==0 && c[l-1][r]==0){
	      c[l][r]=2;
	 	  max++;
		  row(r+3,l);
		  c[l][r]=0;
		  max--;
		  row(r+1,l);
		  }
          else{
			  if(b[l][r]==0 && c[l-1][r]!=0){
              c[l][r]=c[l-1][r]-1;
			  row (r+1,l);
			  }
		  
		      else{
		       row(r+1,l);
			  }
		  }
		  }
		  else
          row (1,l+1);


		
		}
		else
			if(maxt<max){
			maxt=max;
			}
		
}
else
return;	

}





////////////////////////////////////////


int main(){
cin>>ll;
cin>>ww;
for (i=1;i<=ll;i++){
	for (j=1;j<=ww;j++){
	cin>>a[i][j];
	if (a[i][j]=='P') {
		b[i][j]=0;
		c[i][j]=0;
	}
	else {
		b[i][j]=1;
	    c[i][j]=0;
	}
	}
}

/////////////////////////////////////////////
row(1,1);
cout<<maxt;
cout<<endl;
	
	
	
	
	
	
	


















	
	
	/*for (i=3;i<=ll+2;i++){
		for (j=3;j<=ww+2;j++){
			if (b[i][j]==0) {
				c[i][j]=b[i][j+1]+b[i][j+2]+b[i][j-1]+b[i][j-2]+b[i+1][j]+b[i+2][j]+b[i-1][j]+b[i-2][j];
		        pn++;
			}
	
		}
	}
int max=0,maxl,maxw,total=0,flag=0;
	for(k=1;k<=pn;k++){
		for (i=3;i<=ll+2;i++){
			for (j=3;j<=ww+2;j++){
				if (b[i][j]==0 && c[i][j]>max){
				max=c[i][j];
				maxl=i;
				maxw=j;
				flag=1;
				} 
			}	
		
		}
	if (flag==1)
	total++;
	flag=0;
	max=0;
	b[maxl][maxw]=1;
	b[maxl][maxw+1]=1;
	b[maxl][maxw+2]=1;
	b[maxl][maxw-1]=1;
	b[maxl][maxw-2]=1;
	b[maxl+1][maxw]=1;
	b[maxl+2][maxw]=1;
	b[maxl-1][maxw]=1;
	b[maxl-2][maxw]=1;
	int ii,jj;
    for (ii=3;ii<=ll+2;ii++){
		for (jj=3;jj<=ww+2;jj++){
			if (b[ii][jj]==0) {
				c[ii][jj]=b[ii][jj+1]+b[ii][jj+2]+b[ii][jj-1]+b[ii][jj-2]+b[ii+1][jj]+b[ii+2][jj]+b[ii-1][jj]+b[ii-2][jj];
		        }
	
		}
	}




	}

cout<<total;
cout<<endl;*/


return 0;
}

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