本文主要是介绍Tempter of the Bone II HDU - 2128，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Tempter of the Bone II
题目链接：HDU - 2128题意：在迷宫中由起点走到终点， 可以用炸弹炸墙；
结构体中多加一个mp存每个状态下的地图（原图不能改 ）；
还有就是vis加一个最高值， 就是说每个状态可能走多次， 搜的题解是20， 我试了一下不同的值发现最小要大于12；但没弄能这个值是怎么计算出的；
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int N, M, s_x, s_y, e_x, e_y;
char G[10][10];
int vis[10][10][600];
struct node{int x, y, ex, step;char mp[10][10];bool operator < (const node &a) const{return step>a.step;}
};
int dir[4][2]={1, 0, 0, 1, -1, 0, 0, -1};
priority_queue<node> que;
void bfs(){while(!que.empty()) que.pop();node temp;temp.x=s_x, temp.y=s_y, temp.ex=0, temp.step=0, temp.step=0;for(int i=0; i<N; i++){for(int j=0; j<M; j++){temp.mp[i][j]=G[i][j];}}que.push(temp);vis[s_x][s_y][0]++;while(!que.empty()){temp=que.top();if(temp.x==e_x&&temp.y==e_y){printf("%d\n", temp.step);return;}for(int i=0; i<4; i++){temp.step++;temp.x+=dir[i][0];temp.y+=dir[i][1];if(temp.x<N&&temp.x>=0&&temp.y<M&&temp.y>=0&&vis[temp.x][temp.y][temp.ex]<=20){//这里我试了试最小可以改成13;但不知原因if(temp.mp[temp.x][temp.y]=='X'&&temp.ex>0){vis[temp.x][temp.y][temp.ex]++;temp.ex--;temp.mp[temp.x][temp.y]='.';vis[temp.x][temp.y][temp.ex]++;temp.step++;que.push(temp);}else if(temp.mp[temp.x][temp.y]=='.'){vis[temp.x][temp.y][temp.ex]++;que.push(temp);}else if(temp.mp[temp.x][temp.y]<='9'&&temp.mp[temp.x][temp.y]>='0'){vis[temp.x][temp.y][temp.ex]++;temp.ex+=temp.mp[temp.x][temp.y]-'0';temp.mp[temp.x][temp.y]='.';vis[temp.x][temp.y][temp.ex]++;que.push(temp);}}temp=que.top();}que.pop();}printf("-1\n");return;
}
int main(){while(scanf("%d%d", &N, &M), N&&M){for(int i=0; i<N; i++){scanf("%s", G[i]);for(int j=0; j<M; j++){if(G[i][j]=='S') s_x=i, s_y=j, G[i][j]='.';if(G[i][j]=='D') e_x=i, e_y=j, G[i][j]='.';}}memset(vis, 0, sizeof(vis));bfs();}return 0;
}这篇关于Tempter of the Bone II HDU - 2128的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
