The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

杭州现场赛 B题 状态压缩DP

其实思路很简单,只是敲代码的时候很容易敲错,MD,居然为了一个Pn>=n写成了Pn>n NC地检查了一个上午。如果是现场就悲剧了。。。

#include<iostream>
#include
<queue>
#include
<algorithm>
using namespace std;

#define INF 1000000000
int const maxn=15;

struct position{
    
int x,y;
}
pos[maxn];


int dp[1<<maxn][maxn];//初始时候为-1
int sx,sy;
int mat[maxn][maxn];//存地图
int index[maxn][maxn];//存标号,初始为-1
int n,m;
int Pn,Gn;//开关数,能量数

void input()//n,m已存
{
    memset(mat,
0,sizeof(mat));
    
for(int i=0;i<n;i++){
        
char s[100];
        scanf(
"%s",s);
        
for(int j=0;j<m;j++){
            
if(s[j]=='S')mat[i][j]=0;
            
else if(s[j]=='F'){sx=i;sy=j;mat[i][j]=0;}
            
else if(s[j]=='G'){mat[i][j]=1;}
            
else if(s[j]=='Y'){mat[i][j]=2;}
            
else if(s[j]=='D'){mat[i][j]=-1;}
        }

    }

}


int ind;
void getIndex()
{
    ind
=0;
    memset(index,
-1,sizeof(index));
    
for(int i=0;i<n;i++)
        
for(int j=0;j<m;j++){
            
if(mat[i][j]==2)
            
{
                pos[ind].x
=i;
                pos[ind].y
=j;
                index[i][j]
=ind++;
            }

        }

        Pn
=ind;
        
for(int i=0;i<n;i++)
        
for(int j=0;j<m;j++){
            
if(mat[i][j]==1)
            
{
                pos[ind].x
=i;
                pos[ind].y
=j;
                index[i][j]
=ind++;
            }

        }

    Gn
=ind-Pn;
}


struct node
{
    
int x,y;
    
int step;
    node (
int xx,int yy,int ss){x=xx;y=yy;step=ss;}
    node ()
{}
}
;

bool god(int x,int y){
    
if(x>=0&&x<n&&y>=0&&y<m&&mat[x][y]!=-1)return true;
    
else return false;
}

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int v[maxn][maxn];
int dis[maxn][maxn];
void predo(int i)//预处理出最短路
{
    memset(v,
0,sizeof(v));
    
for(int j=0;j<ind;j++)
        dis[i][j]
=INF;
    queue
<node>Q;
    node t(pos[i].x,pos[i].y,
0);
    v[t.x][t.y]
=1;
    Q.push(t);
    
//
    while(!Q.empty())
    
{
        t
=Q.front();Q.pop();
        
if(index[t.x][t.y]!=-1)
            dis[i][index[t.x][t.y]]
=t.step;
        
for(int i=0;i<4;i++)
        
{
            
int nx=t.x+dir[i][0];
            
int ny=t.y+dir[i][1];
            
if( god(nx,ny)&& (!v[nx][ny]) )
            
{
                node nt(nx,ny,t.step
+1);
                Q.push(nt);
                v[nx][ny]
=1;
            }

        }

    }

}



bool DP(int mid)
{
    
int  nn=(1<<ind);
    
for(int j=0;j<nn;j++){
        
for(int i=0;i<ind;i++){
            
if(dp[j][i]!=-1)
            
{
                
for(int k=0;k<ind;k++)
                
{
                    
int test=1<<k;
                    
if(j&test)continue;
                    
if(dp[j][i]>=dis[i][k])
                    
{
                        
int nstate=j|test;
                        dp[nstate][k]
=max(dp[nstate][k],dp[j][i]-dis[i][k]);
                        
if(k>=Pn) dp[j|test][k]=mid;
                        
//
                        int K=(1<<Pn)-1;
                        
if(((j|test)&K)==K)
                            
return true;
                    }


                }

            }

        }

    }

    
return false;
}


void init(int mid)//预处理出F到达其他各点最短路
{
    memset(v,
0,sizeof(v));
    memset(dp,
-1,sizeof(dp));
    queue
<node>Q;
    
//
    node t(sx,sy,0);
    Q.push(t);
    v[sx][sy]
=1;
    
while(!Q.empty())
    
{
        node t
=Q.front();Q.pop();
        
int k=index[t.x][t.y];
        
if(k!=-1){
            
if(t.step<=mid)
            
{
                dp[
1<<k][k]=mid-t.step;
                
if(mat[t.x][t.y]==1)
                    dp[
1<<k][k]=mid;
            }

        }

        
//
        for(int i=0;i<4;i++){
            
int nx=t.x+dir[i][0];
            
int ny=t.y+dir[i][1];
            
if( god(nx,ny) && (!v[nx][ny]) )
            
{
                node nt(nx,ny,t.step
+1);
                Q.push(nt);
                v[nx][ny]
=1;
            }

        }

    }

    
//
}




int main()
{

    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        
if(n==0&&m==0)
            
break;
        input();
        getIndex();
        
for(int i=0;i<ind;i++)predo(i);
        
int l=1;
        
int r=215;//记得改回来
        int ans=-1;
        
while(l<=r)
        
{
            
int mid=(l+r)>>1;
            init(mid);
            
if(DP(mid)){
                r
=mid-1;
                ans
=mid;
            }

            
else
                l
=mid+1;
        }

        printf(
"%d\n",ans);
    }

    
return 0;
}



 

posted on 2010-11-09 15:35 abilitytao 阅读(340) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理