去年做杭州網(wǎng)賽的時(shí)候遇到的題目，當(dāng)時(shí)一點(diǎn)思路都沒有，過后一直沒去做，今天看了一下，發(fā)現(xiàn)其實(shí)和hdu的1044很像，可以先縮圖，然后bfs，我用了兩次bfs實(shí)現(xiàn)。具體思路是對(duì)于每一個(gè)非墻非走廊的點(diǎn)進(jìn)行bfs，擴(kuò)展和它相鄰的非墻非走廊的點(diǎn)，保存到鄰接表中，然后對(duì)于所有邊界上是gate的點(diǎn)進(jìn)行bfs，用優(yōu)先隊(duì)列實(shí)現(xiàn)，狀態(tài)為三維，即坐標(biāo)+內(nèi)力，其實(shí)可以將每個(gè)點(diǎn)離散化到一個(gè)數(shù)字，以減少內(nèi)存開銷來換取時(shí)間。
代碼如下：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = 
{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct point {
int x;
int y;
int num;
int step;
bool friend operator < (point a, point b) {
return a.step > b.step;
}
}temp, tt;
char map[110][110];
vector < point > vec[101][101];
int n, m;
int hash[101][101];
priority_queue < point > q;
__int8 visit[100][100][27];
int ans;
//縮圖
void bfs(int x, int y) {
int i;
temp.x = x;
temp.y = y;
memset(hash, 0, sizeof(hash));
while(!q.empty() )
q.pop();
q.push( temp );
hash[ temp.x ][ temp.y ] = 1;
while(!q.empty()) {
temp = q.top();
q.pop();
for(i = 0; i < 4; i++) {
tt.x = temp.x + dir[i][0];
tt.y = temp.y + dir[i][1];
if(tt.x < 0 || tt.y < 0 || tt.x == n || tt.y == m)
continue;
if(map[tt.x][tt.y] == '*')
continue;
if(map[tt.x][tt.y] >= 'A' && map[tt.x][tt.y] <= 'Z')
continue;
if(map[tt.x][tt.y] == '#')
continue;
if(hash[ tt.x ][ tt.y ])
continue;
if(!hash[ tt.x ][ tt.y ] ) {
hash[ tt.x ][ tt.y ] = 1;
if(map[tt.x][tt.y] == '.')
q.push( tt );
else {
vec[x][y].push_back( tt );
}
}
}
}
}
//求最短距離
int BFS(int x, int y, int num) {
int i;
temp.step = 0;
temp.x = x;
temp.y = y;
temp.num = num;
while(!q.empty())
q.pop();
memset(visit, -1, sizeof(visit));
q.push( temp );
visit[ temp.x ][ temp.y ][ temp.num ] = 0;
while( !q.empty() ) {
temp = q.top();
q.pop();
if(temp.step > ans && ans != -1)
return -1;
if( map[ temp.x ][ temp.y ] == '$')
return temp.step;
int size = vec[ temp.x ][ temp.y ].size();
for(i = 0; i < size; i++) {
point rt = vec[ temp.x ][ temp.y ][ i ];
if(map[rt.x][rt.y] == '$') {
tt.num = temp.num;
tt.step = temp.step;
tt.x = rt.x;
tt.y = rt.y;
if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
|| visit[ tt.x ][ tt.y ][ tt.num ] == -1) {
visit[ tt.x ][ tt.y ][ tt.num ] = tt.step;
q.push( tt );
}
continue;
}
if(temp.num) {
tt.num = temp.num - 1;
tt.step = temp.step;
tt.x = rt.x;
tt.y = rt.y;
if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
|| visit[ tt.x ][ tt.y ][ tt.num ] == -1) {
visit[ tt.x ][ tt.y ][ tt.num ] = tt.step;
q.push( tt );
}
}
tt.num = temp.num;
tt.step = temp.step + map[rt.x][rt.y] - '0';
tt.x = rt.x;
tt.y = rt.y;
if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
|| visit[ tt.x ][ tt.y ][ tt.num ] == -1) {
visit[ tt.x ][ tt.y ][ tt.num ] = tt.step;
q.push( tt );
}
}
}
return -1;
}
int main() {
int i, j;
while(1) {
while(gets(map[0])) {
if( strcmp(map[0], "") )
break;
}
m = strlen( map[0] );
if(strcmp(map[0], "--") == 0)
break;
n = 1;
while(gets(map[n])) {
if(strcmp( map[n], "" ) == 0)
break;
else
n ++;
}
for(i = 0; i < n; i++) {
for(j = 0;j < m; j++)
vec[i][j].clear();
}
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(map[i][j] >= '1' && map[i][j] <= '9') {
bfs(i, j);
}
if(map[i][j] >= 'A' && map[i][j] <= 'Z' || map[i][j] == '#') {
bfs(i, j);
}
}
}
ans = -1;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(map[i][j] >= 'A' && map[i][j] <= 'Z') {
int ty = BFS(i, j, map[i][j]-'A'+1);
if(ty != -1) {
if(ty < ans || ans == -1)
ans = ty;
}
}
if(map[i][j] == '#') {
int ty = BFS(i, j, 0);
if(ty != -1) {
if(ty < ans || ans == -1)
ans = ty;
}
}
}
}
if(ans == -1)
printf("IMPOSSIBLE\n");
else
printf("%d\n", ans);
}
return 0;
}