首页 > 代码库 > HDU1429 胜利大逃亡(续) BFS +简单状压
HDU1429 胜利大逃亡(续) BFS +简单状压
把手中持有的钥匙状态状压一下即可,然后vis访问标记的时候,开个三维,多一维即为当前持有钥匙状态,这样就能祛除重复标记困难走点的问题,跟网络赛那题很像,网络赛的更难点,这个简单点
int n,m,t; int sx,sy,ex,ey; char mp[20 + 55][20 + 55]; bool vis[20 + 5][20 + 5][(1<<10) + 5]; int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; struct Node { int now;//现在钥匙状态 int x,y; int step; friend bool operator<(Node aa,Node bb) { return aa.step > bb.step; } }; void init() { memset(vis,false,sizeof(vis)); } bool input() { while(cin>>n>>m>>t) { for(int i=0;i<n;i++) { scanf("%s",mp[i]); for(int j=0;j<m;j++) { if(mp[i][j] == '@')sx = i,sy = j; if(mp[i][j] == '^')ex = i,ey = j; } } return false; } return true; } int ans; void bfs(int x,int y) { queue<Node> q; Node ss,ee; ss.x = x,ss.y = y,ss.step = 0,ss.now = 0; q.push(ss); vis[ss.x][ss.y][0] = true; while(!q.empty()) { ss = q.front(); q.pop(); if(ss.step >= t)continue; if(ss.x == ex && ss.y == ey) { ans = min(ans,ss.step); break; } for(int i=0;i<4;i++) { int dx = ss.x + dir[i][0]; int dy = ss.y + dir[i][1]; if(dx < 0 || dx >= n || dy < 0 || dy >= m)continue; if(mp[dx][dy] == '*')continue; if(vis[dx][dy][ss.now])continue; ee.now = ss.now; if(mp[dx][dy] >= 'A' && mp[dx][dy] <= 'J') {/*遇到门*/ int tmp = mp[dx][dy] - 'A'; if((ss.now&(1<<tmp)) == 0)continue; } if(mp[dx][dy] >= 'a' && mp[dx][dy] <= 'z') {/*遇到钥匙*/ int tmp = mp[dx][dy] - 'a'; ee.now |= (1<<tmp); } ee.x = dx,ee.y = dy,ee.step = ss.step + 1; vis[dx][dy][ss.now] = true; q.push(ee); } } } void cal() { ans = inf; bfs(sx,sy); if(ans == inf || ans >= t)puts("-1"); else cout<<ans<<endl; } void output() { } int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0; }
HDU1429 胜利大逃亡(续) BFS +简单状压
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。