问题 B: 瞎子与瘸子的故事
时间限制:
1Sec 内存限制:
128MB
提交: 25 解决:
6
[提交][状态][讨论版]
题目描述
瞎子和瘸子两人共骑一辆摩托车，瞎子骑，瘸子看路，一路无事。
转过一道弯，瘸子忽然发现路上有一道沟，连忙大声喊道：“沟！沟！沟！”
瞎子一听来了劲，接着唱道：“啊涞，啊涞，啊涞……”
结果瞎子和瘸子两人连人带车一起跌进沟内。
上次的事故使瘸子不幸离开人世，瞎子却因祸得福，用瘸子的眼角膜进行了移植手术，瞎子终于重见光明；离开医院的瞎子抱着瘸子的骨灰前往瘸子的家乡安葬瘸子；那么问题就来了。
输入
输入第一个数T，T组测试数据。
两个数 n, m; ( 0< n , m <= 100 )
表示一个n行m列的二维地图。
接下来n行每行m
个字符。
‘s’ 表示瞎子目前所在位置。
‘# ’表示此处为一座山。为了节省体力，不从此处通行。
从‘A’-‘Z’表示各地的经济水平，对应1-26，路过对应字符的地区需要交对应的生活费。
‘l’表示瘸子家乡的所在地。
s 与 l
均为小写字母。
瞎子只能走四个方向。
输出
输出一个数表示瞎子到达瘸子故乡需要的生活费最小是多少。
如果不能到达，输出 -1。
样例输入
3
3 5
#sVGF
A##ZA
lCDBC
3 3
sAB
ABS
ABl
3 3
s#B
###
ABl
样例输出
48
4
-1
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX_N 100
#define MAX(a, b) (a > b)? a: b
#define MIN(a, b) (a < b)? a: b
using namespace std;
char map[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];
struct node{
int x;
int y;
int step;
friend bool operator < (node a, node b)
{
return a.step > b.step;
}
};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m;
int bfs(int x1,int y1, int x2, int y2)
{
priority_queue<node> que;
node temp, next;
temp.x = x1;
temp.y = y1;
temp.step = 0;
vis[temp.x][temp.y] = true;
while(!que.empty()) que.pop();
que.push(temp);
while(que.size()) {
//cout<<"text"<<endl;
temp = que.top();
que.pop();
for (int i = 0; i < 4; i++) {
next.x = temp.x + dx[i];
next.y = temp.y + dy[i];
if (next.x == x2 && next.y == y2) return temp.step;
if (map[next.x][next.y] == '#' || next.x < 0 || next.x >= n|| next.y < 0 || next.y >= m || vis[next.x][next.y])
continue;
vis[next.x][next.y] = true;
next.step = temp.step + map[next.x][next.y] - 'A' + 1;
//cout<<"text"<<" "<<next.x<<" "<<next.y<<" "<<next.step<<endl;
que.push(next);
}
}
return -1;
}
int main()
{
int t, sx, sy, ex, ey;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", &map[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 's') {
sx = i;
sy = j;
}
if(map[i][j] == 'l') {
ex = i;
ey = j;
}
}
}
memset(vis, false, sizeof(vis));
int ans = bfs(sx, sy, ex, ey);
printf("%d
", ans );
}
return 0;
}