解题思路：http://acm.swust.edu.cn/problem/1023/
BH is in a maze,the maze is a matrix,he wants to escape!
The input consists of multiple test cases.
For each case,the first line contains 2 integers N,M( 1 <= N, M <= 100 ).
Each of the following N lines contain M characters. Each character means a cell of the map.
Here is the definition for chracter.
For a character in the map:
'S':BH's start place,only one in the map.
'E':the goal cell,only one in the map.
'.':empty cell.
'#':obstacle cell.
'A':accelerated rune.
BH can move to 4 directions(up,down,left,right) in each step.It cost 2 seconds without accelerated rune.When he get accelerated rune,moving one step only cost 1 second.The buff lasts 5 seconds,and the time doesn't stack when you get another accelerated rune.(that means in anytime BH gets an accelerated rune,the buff time become 5 seconds).
The minimum time BH get to the goal cell,if he can't,print "Please help BH!".
|
5 5
....E
.....
.....
##...
S#...
5 8
........
........
..A....A
A######.
S......E
|
|
Please help BH!
12
|
由于OJ上传数据的BUG,换行请使用"\r\n"，非常抱歉
题目大意：一个迷宫逃离问题，只是有了加速符A,正常情况下通过一个格子2s,有了加速符只要1s,并且加速符持续5s,‘S'代表起点
'E'代表终点，'#'代表障碍，'.'空格子，能够逃离输出最少用时，否则输出"Please help BH!"
解题思路：BFS，用一个3维dp数组存贮，每一点在不同加速状态下的值，然后筛选dp数组终点的最小值即可
代码如下：
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; #define maxn 101
#define inf 0x3f3f3f3f int dir[][] = { , , , , -, , , - };
int dp[maxn][maxn][];
int sx, sy, ex, ey, n, m;
char map[maxn][maxn]; struct node{
int x, y, step, speed;//spead加速
};
void bfs(){
node now, next;
now.x = sx, now.y = sy, now.step = , now.speed = ;
dp[sx][sy][] = ;
queue<node>Q;
Q.push(now);
while (!Q.empty()){
now = Q.front(); Q.pop();
for (int i = ; i < ; i++){
next = now;
next.x += dir[i][];
next.y += dir[i][];
if (next.x < || next.x >= n || next.y < || next.y >= m || map[next.x][next.y] == '#')continue;//不可行状态
if (next.speed){
//加速效果
next.speed--;
next.step++;
}
else next.step += ;
if (map[next.x][next.y] == 'A')next.speed = ;//获得加速神符
if (next.step < dp[next.x][next.y][next.speed]){
dp[next.x][next.y][next.speed] = next.step;
Q.push(next);
}
}
}
int ans = inf;
for (int i = ; i >= ; i--)
ans = min(ans, dp[ex][ey][i]);
if (ans >= inf)
cout << "Please help BH!\r\n";
else
cout << ans << "\r\n";
}
int main(){
while (cin >> n >> m){
memset(dp, inf, sizeof dp);
for (int i = ; i < n; i++){
cin >> map[i];
for (int j = ; j < m; j++){
if (map[i][j] == 'S')sx = i, sy = j;
if (map[i][j] == 'E')ex = i, ey = j;
}
}
bfs();
}
return ;
}