本文共 1640 字，大约阅读时间需要 5 分钟。
题意：从K走到T，S为怪，走的时候就多花费一秒，走到T时收集m把不同的钥匙，但是规定收集n之前，必须1~n-1全部收集完毕，怪最多有5个
思路：怪最多就有5个，然后钥匙是1~9把，我们每个点的状态就不会很多，在BFS时每个点的状态进行标记就行了，5个怪状态压缩着判断，因为这个怪在第二次经过的时候已经死了，不用花费时间去杀死它
//// main.cpp// dfs-bfs搜索//// Created by liuzhe on 16/8/10.// Copyright © 2016年 my_code. All rights reserved.//#include #include #include #include #include using namespace std;const int maxn=110;const int inf = 0x3f3f3f3f;int sx,sy,ex,ey,n,m,cnt;int dir[4][2]={ {0,1},{0,-1},{1,0},{-1,0}};int vis[maxn][maxn][10][40];char str[maxn][maxn];struct edge{ int x,y,step,numkey,ss;};struct snake{ int x,y;}sna[10];int bfs(){ queue que; edge c,ne; memset(vis,0,sizeof(vis)); c.x = sx; c.y = sy; c.step = 0; c.numkey = 0; c.ss = 0; vis[c.x][c.y][0][0] = 1; que.push(c); int ans = inf; while(!que.empty()) { c = que.front(); que.pop(); if(c.x==ex&&c.y==ey&&c.numkey==m) ans = min(ans,c.step); for(int i=0;i<4;i++) { int xx = c.x + dir[i][0]; int yy = c.y + dir[i][1]; if(xx<0||xx>n-1||yy<0||yy>n-1||str[xx][yy]=='#') continue; if(vis[xx][yy][c.numkey][c.ss]) continue; ne.x = xx; ne.y = yy; ne.step = c.step+1; ne.numkey = c.numkey; ne.ss = c.ss; if(str[xx][yy]>='1'&&str[xx][yy]<='9')//如果走到的位置是钥匙就进行判断 { int t = str[xx][yy] - '0'; if(ne.numkey==t-1)//钥匙刚好是当前钥匙数＋1，就符合条件 { ne.numkey++; vis[ne.x][ne.y][ne.numkey][ne.ss] = 1; que.push(ne); } else//不符合条件直接压进队列 { vis[ne.x][ne.y][ne.numkey][ne.ss] =1; que.push(ne); } } else if(str[xx][yy]=='S')//meet snake,then judge { for(int i=0;i >i)&1)//说明这个已经死掉了 { vis[ne.x][ne.y][ne.numkey][ne.ss] = 1; que.push(ne); } else//时间加一，状态更新 { ne.step++; ne.ss+=(1<
转载地址：http://kpali.baihongyu.com/