Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
测试数据过了,但总是wrong answer,我用的是搜索,加了个可行性剪枝,请高手看一下,谢了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator