| ||||||||||
| 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