# HDU 2416 Treasure of the Chimp Island

2019/7/23 4:11:46 人评论 次浏览 分类：学习教程

```#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;

const int maxn = 110;
const int INF = 0x3f3f3f3f;

char map[maxn][maxn];
int Time[maxn][maxn][27];

int n, m;

vector<pair<int, int> > pos;

int bx, by;
int ex, ey;

struct node
{
int x, y;
int step, dn;
};

int check(int x, int y)
{
if(x >= 0 && x < n && y >= 0 && y < m && map[x][y] != '*') return 1;
return 0;
}

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

void bfs(int &ans)
{
queue<node> Q;

node cur, next;

for(int i = 0; i < pos.size(); i++)
{
cur.x = pos[i].first/m, cur.y = pos[i].first%m;
cur.step = 0, cur.dn = pos[i].second;
Q.push(cur);
}

while(!Q.empty())
{
cur = Q.front(); Q.pop();
int x = cur.x, y = cur.y, step = cur.step, dn = cur.dn;
for(int i = 0; i < 4; i++)
{
next = cur;
int newx = x+dx[i], newy = y+dy[i];
if(!check(newx, newy)) continue;

if((map[newx][newy] == '.' && Time[newx][newy][dn] > step))
{
next.x = newx, next.y = newy;
next.step = step, next.dn = dn;
Time[newx][newy][dn] = step;
Q.push(next);
}
else if(isdigit(map[newx][newy]))
{
if((Time[newx][newy][dn] > step+map[newx][newy]-'0'))
{
next.x = newx, next.y = newy;
next.step = step+map[newx][newy]-'0', next.dn = dn;
Time[newx][newy][dn] = step+map[newx][newy]-'0';
Q.push(next);
}
if((dn >= 1 && Time[newx][newy][dn-1] > step))
{
next.x = newx, next.y = newy;
next.step = step, next.dn = dn-1;
Time[newx][newy][dn-1] = step;
Q.push(next);
}
}
else if(map[newx][newy] == '\$' && step < ans)
ans = step;
}
}
}

void init()
{
pos.clear();
}

void build()
{
memset(Time, INF, sizeof(Time));

for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(map[i][j] == '\$') ex = i, ey = j;
if(isalpha(map[i][j]) || map[i][j] == '#')
{
int t;
if(map[i][j] == '#') t = 0;
else t = map[i][j]-'A'+1;
pos.push_back(make_pair(i*m+j, t));
map[i][j] = '*';
Time[i][j][t] = 0;
}
}
}
}

void rebuild()
{
int ans = INF;
bfs(ans);
if(ans == INF) { printf("IMPOSSIBLE\n"); }
else printf("%d\n", ans);
}

int main()
{
for(;;)
{
init();
n = 0;
scanf("%s%*c", map[n]);
if(strcmp(map[n], "--") == 0) break;
n++;

while(gets(map[n]))
{
if(strlen(map[n]) == 0) break;
n++;
}

m = strlen(map[n-1]);

build();
rebuild();
}
return 0;
}```
View Code

暂无相关的资讯...

-->