HDU 1429 胜利大逃亡(续) - c++编程基础

请不要随便指点别人该怎么做、每个人的人生都应该自己掌握、你给不了别人一切、你也不懂别人的忧伤、

微笑不代表快乐、哭泣不一定悲伤

不努力怎么让关心你的人幸福、不努力怎么让看不起你的人绝望、

我用生命在奋斗――lx_Zz

―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

――――――――――――――――――――――――― 华丽的分割线 ――――――――――――――――――――――――――――

―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

10775294

2014-05-20 19:59:13

Accepted

1429

437MS

2336K

2372 B

G++

给我再去相....

水题、标记多状态就行、

虽然是1A、、但是手速弱的一B、、、

/* 题目： HDU 1429    */
/* 作者： lx_Zz       */
/* 时间： 2014.5.20   */
#include
  
   
#include
   
     #include
    
      #include
      #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             using namespace std; #define INF 0x7fffffff #define LL __int64 int dir[4][2]={0,1,1,0,-1,0,0,-1}; int vis[21][21][1<<10]; char mpt[21][21]; int n,m,t; struct node { int x,y; int state; int step; }; int BFS(int sx,int sy,int ex,int ey) { int ans=-1; memset(vis,0,sizeof(vis)); vis[sx][sy][0]=1; queue
            
             q; node now,next; now.x=sx;now.y=sy; now.state=0;now.step=0; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(now.x==ex&&now.y==ey) { ans=now.step;break; } for(int i=0;i<4;i++) { int tx=now.x+dir[i][0]; int ty=now.y+dir[i][1]; if(tx<1||ty<1||tx>n||ty>m)continue; if(mpt[tx][ty]=='*')continue; else if(vis[tx][ty][now.state]==0&&(mpt[tx][ty]=='.'||mpt[tx][ty]=='^'||mpt[tx][ty]=='@')) { next.x=tx; next.y=ty; next.state=now.state; next.step=now.step+1; vis[tx][ty][now.state]=1; q.push(next); } else if(vis[tx][ty][now.state]==0&&(mpt[tx][ty]>='a'&&mpt[tx][ty]<='z')) { vis[tx][ty][now.state]=1; int temp=1<<(mpt[tx][ty]-'a'); next.x=tx; next.y=ty; next.state=now.state|temp; next.step=now.step+1; q.push(next); } else if(vis[tx][ty][now.state]==0&&(mpt[tx][ty]>='A'&&mpt[tx][ty]<='Z')) { vis[tx][ty][now.state]=1; int temp=1<<(mpt[tx][ty]-'A'); if(now.state&temp) { next.x=tx; next.y=ty; next.state=now.state; next.step=now.step+1; q.push(next); } } } } return ans; } int main() { //freopen("C:\\Users\\终将我要华丽的逆袭\\Desktop\\lx_Zz_in.txt","r",stdin); //freopen("C:\\Users\\终将我要华丽的逆袭\\Desktop\\lx_Zz_out.txt","w",stdout); while(scanf("%d%d%d",&n,&m,&t)!=EOF) { int sx,sy; int ex,ey; for(int i=1;i<=n;i++) { scanf("%s",mpt[i]+1); for(int j=1;j<=m;j++) { if(mpt[i][j]=='@') { sx=i;sy=j; } if(mpt[i][j]=='^') { ex=i;ey=j; } } } int ans=BFS(sx,sy,ex,ey); if(ans