首页 > 代码库 > HDU 1429 胜利大逃亡(续)
HDU 1429 胜利大逃亡(续)
请不要随便指点别人该怎么做、每个人的人生都应该自己掌握、你给不了别人一切、你也不懂别人的忧伤、
微笑不代表快乐、哭泣不一定悲伤
不努力怎么让关心你的人幸福、不努力怎么让看不起你的人绝望、
我用生命在奋斗——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<cstdio> #include<queue> #include<vector> #include<map> #include<string> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> 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<node>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<t) printf("%d\n",ans); else printf("-1\n"); } return 0; }