| ||||||||||
| 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 | |||||||||
自认为还可以的代码 AC的哦。。#include "stdio.h"
#include "memory.h"
int map[102];
int possible[60],N,M,t,length[60],dp[60][60][102];
int main(void)
{
t=0;
int i,k,j,l,max;
char c;
scanf("%d%d",&N,&M);
scanf("\n");
map[0]=map[1]=0;
memset(dp,-1,sizeof(dp));
for(i=0;i!=N;++i)
{
for(j=0;j!=M;++j)
if(scanf("%c",&c)==1&&c=='P')
map[i+2]+=1<<(M-j-1);
scanf("%c",&c);
}
k=1<<M;
for(i=0;i!=k;++i)
if(!(i>>1&i||i>>2&i))
possible[t++]=i;
for(i=0;i!=t;++i)
{
k=0;
for(j=0;j!=M;++j)
if(possible[i]&(1<<j))
k++;
length[i]=k;
}
dp[0][0][1]=0;
for(i=1;i!=N+1;++i)
{
for(j=0;j!=t;++j)
{
if((possible[j]&map[i])!=possible[j]) continue;
for(k=0;k!=t;++k)
{
max=0;
if((possible[k]&map[i+1])!=possible[k]||possible[j]&possible[k]) continue;
for(l=0;l!=t;++l)
{
if((possible[l]&map[i-1])!=possible[l]||possible[j]&possible[l]||possible[k]&possible[l]) continue;
max=dp[l][j][i]>max?dp[l][j][i]:max;
}
dp[j][k][i+1]=max+length[k];
}
}
}
max=0;
for(i=0;i!=t;++i)
for(j=0;j!=t;++j)
max=max<dp[i][j][N+1]?dp[i][j][N+1]:max;
printf("%d\n",max);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator