HDU 1072 Nightmare
bfs问题。
走迷宫,有炸弹时限,有重置炸弹时间的机器。
注意有些位置走过之后,按了重置器后依然可以入队。所以检查变成 vis[][][]三维的。
当然同一个重置器反复去走也没有意义,所以重置器检查 rest[][]。
走到重置器的时候,炸弹时间变回去,路径时间+1,重置器rest[][]=1
其他时候炸弹时间-1,路径时间+1
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,n) for(int i= a;i< n ;i++) #define debug puts("==fuck==") #define acfun std::ios::sync_with_stdio(false) #define SIZE 1000+10 using namespace std; int xx[]={0,0,-1,1}; int yy[]={-1,1,0,0}; int n,m; int g[10][10]; struct lx { int x,y; int lv,t; int re; void init(int xx,int yy,int tt,int llv,int rest) { x=xx,y=yy,t=tt,lv=llv,re=rest; } }; lx start,thend; void bfs() { queue<lx>q; q.push(start); bool vis[10][10][65]; bool rest[10][10]; CLR(vis,0); CLR(rest,0); vis[start.x][start.y][0]=1; while(!q.empty()) { lx tmp=q.front(); q.pop(); vis[tmp.x][tmp.y][tmp.re]=1; if(tmp.x==thend.x&&tmp.y==thend.y) { printf("%d\n",tmp.lv); return ; } // printf("%d %d %d %d=\n",tmp.x,tmp.y,tmp.t,tmp.lv); // system("pause"); FOR(k,0,4) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; if(x<0||x>=n||y<0||y>=m||g[x][y]==0||tmp.t==1||rest[x][y]) continue; lx now; if(g[x][y]==4) { now.init(x,y,6,tmp.lv+1,tmp.re+1); rest[x][y]=1; } else now.init(x,y,tmp.t-1,tmp.lv+1,tmp.re); if(vis[x][y][now.re])continue; q.push(now); } } printf("-1\n"); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); FOR(i,0,n) FOR(j,0,m) { scanf("%d",&g[i][j]); if(g[i][j]==2) start.init(i,j,6,0,0); else if(g[i][j]==3) thend.init(i,j,0,0,0); } bfs(); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。