刺客信条

题目

小A在玩游戏《刺客信条2》。按照刺客信条2的剧情，艾吉奥需要前往威尼斯，从圣殿骑士手里夺取金苹果，然后前往罗马梵蒂冈刺杀教皇，拿取伊甸园神器“教皇权杖”。
但是由于小A已经玩过很多次这个游戏了，他对剧情和地图了如指掌，现在已经轻而易举地拿到了金苹果，返回到了佛罗伦萨的庄园。

接下来，小A就将操控艾吉奥从佛罗伦萨庄园出发，前往梵蒂冈，夺取教皇权杖。
在整个过程中，每经过一个建筑，都需要花费一定的时间，需要特别注意的是，由于圣母百花大教堂、圣马可大教堂、乔托钟楼都有众多圣殿骑士守护，经过这三个地方时，需要花费 100 的时间。
请计算，从佛罗伦萨庄园到梵蒂冈，最快需要多少时间？

输入描述:

第一行有两个整数，表示地图的行数n和列数m，地图为一个n×m的矩阵。
接下来有n行，每行m个字符，每个字符是一个数字或大写字母，数字表示经过该建筑需要的时间，字母表示特定建筑。
S表示佛罗伦萨的庄园，即起点；E表示梵蒂冈，即终点；A表示圣母百花大教堂；B表示圣马可大教堂；C表示乔托钟楼；A、B、C在每组数据中至多出现一次，每个字符或数字之间用空格分隔。
0≤n,m≤30

解题思路

使用 BFS：

使用 函数计算从起点到矩阵其他点的最短距离。注意实时更新最短距离。

C++代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int inf = 0x3f3f3f3f;
int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int n, m;

vector<vector<int>> bfs(vector<vector<int>>& ground, int sx, int sy){
    vector<vector<int>> cost(n, vector<int>(m, inf));
    queue<pair<int,int>> que;
    cost[sx][sy] = 0;
    que.push(make_pair(sx,sy));
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for(int i=0; i<4; ++i){
            int a = x + d[i][0];
            int b = y + d[i][1];
            if(a>=0 && a<n && b>=0 && b<m && cost[a][b]>cost[x][y]+ground[a][b]){
                cost[a][b] = cost[x][y] + ground[a][b];
                que.push(make_pair(a,b));
            }
        }
    }
    return cost;
}

int main(){
    cin >> n >> m;
    vector<vector<int>> ground(n, vector<int>(m,0));
    int sx, sy, ex, ey;
    char ch;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin >> ch;
            if(ch>='0' && ch<='9')
                ground[i][j] = ch-'0';
            else if(ch=='S'){
                sx = i;
                sy = j;
            }
            else if(ch=='E'){
                ex = i;
                ey = j;
            }
            else
                ground[i][j] = 100;
        }
    }
    vector<vector<int>> cost = bfs(ground, sx, sy);
    cout << cost[ex][ey] << endl;
    return 0;
}