题意:给最大100*100的地图,$代表财宝,*表示不可达,. 表示走过不需要花费,1~9表示走过需要花费1~9,边界格子为* ,#(表示从此进入可以带0个
炸药)或A~Z(表示从此进入可以带1~26个炸药),现在一个人可以从边界非*处进入,最小到达$位置的最小花费是多少。
题解:如果考虑枚举起点的话,最坏情况边界全部为起点,这样至少100*100*100*100的复杂度就悲剧了。 所以想从$开始bfs 最短路,dis[ i ][ j ][ k ]表示
到达[ i , j ]点已经用k个炸弹的最小花费,注意边界点不入队列即可。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> #include <queue> #define MIN(a , b) ((a) < (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; const int maxn = 102; const int maxm = 27; const int move[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; struct ddd { int x,y,use; int val; ddd(){} ddd(int xx,int yy,int uu,int vv) { x = xx; y = yy; use = uu; val = vv; return; } bool operator < (const ddd &other) const { return val > other.val; } }; priority_queue <ddd> Q; int dis[maxn][maxn][maxm]; bool vis[maxn][maxn][maxm]; char map[maxn][maxn]; int m,n; void init() { memset(vis,false,sizeof(vis)); while(!Q.empty()) Q.pop(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { for(int k=0;k<maxm;k++) { dis[i][j][k] = inf; } if(map[i][j] == '$') { dis[i][j][0] = 0; Q.push(ddd(i,j,0,0)); map[i][j] = '.'; } } } return; } bool judge(int x,int y) { if(x >= 0 && y >= 0 && x < n && y < m && map[x][y] != '*') { return true; } return false; } int bound(int x,int y) { if(x == 0 || y == 0 || x == n-1 || y == m-1) { if(map[x][y] == '#') return 0; else if(map[x][y] >= 'A' && map[x][y] <= 'Z') return map[x][y] - 'A' + 1; return -1; } return -1; } void bfs() { int res = inf; ddd cur; while(!Q.empty()) { cur = Q.top(); Q.pop(); if(vis[cur.x][cur.y][cur.use]) continue; vis[cur.x][cur.y][cur.use] = true; for(int i=0;i<4;i++) { int tx = cur.x + move[i][0]; int ty = cur.y + move[i][1]; if(judge(tx , ty)) { int d = bound(tx , ty); if(d >= 0) { if(d >= cur.use) res = MIN(res , cur.val); continue; } if(map[tx][ty] == '.') { if(vis[tx][ty][cur.use] == false && dis[tx][ty][cur.use] > cur.val) { dis[tx][ty][cur.use] = cur.val; Q.push(ddd(tx , ty , cur.use , cur.val)); } } else { int cost = map[tx][ty] - '0'; if(vis[tx][ty][cur.use] == false && dis[tx][ty][cur.use] > cur.val + cost) { dis[tx][ty][cur.use] = cur.val + cost; Q.push(ddd(tx , ty , cur.use , cur.val + cost)); } if(cur.use < 26 && vis[tx][ty][cur.use + 1] == false && dis[tx][ty][cur.use + 1] > cur.val) { dis[tx][ty][cur.use + 1] = cur.val; Q.push(ddd(tx , ty , cur.use + 1 , cur.val)); } } } } } if(res == inf) puts("IMPOSSIBLE"); else printf("%d\n",res); return; } int main() { while(true) { n = 0; while(gets(map[n])) { if(map[n][0] == '-') return 0; if(map[n][0] == '\0') break; n++; } m = strlen(map[0]); init(); bfs(); } return 0; }