[ Aizu - 0558 ]

大意：在H * W的地图上有N个奶酪工厂，每个工厂分别生产硬度为1-N的奶酪。有一只老鼠准备从出发点吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。 老鼠从当前格到上下左右相邻的无障碍物的格需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。 输入：第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)，之后H行W列为地图， “.“为空地， ”X“为障碍物，”S“为老鼠洞， 1-N代表硬度为1-N的奶酪的工厂。输出最少用时。

Sample Input 1

3 3 1
S..
...
..1

Sample Output 1

4

Sample Input 2

4 5 2
.X..1
....X
.XX.S
.2.X.

Sample Output 2

12

Sample Input 3

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

Sample Output 3

91

题解

BFS变下形就行，注意数组范围……

#include<bits/stdc++.h>
using namespace std;
const int INF = 100000000, maxn = 1005;
//可以使用结构体
typedef pair<int, int> P;

char maze[maxn][maxn];
int n, m, k, sx, sy, gx[10], gy[10];
//到各个位置的最短距离的数组
int d[maxn][maxn];
//4个方向移动的向量
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

//求从(sx,sy)到(gx,gy)的最短距离
//若无法到达则是INF
int bfs(int sx, int sy, int gx, int gy)
{
    queue<P> que;
    //所有的位置都初始化为INF
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            d[i][j] = INF;

    que.push(P(sx, sy)); //将起点加入队列中
    d[sx][sy] = 0;       //并把这一地点的距离设置为0

    //不断循环直到队列的长度为0
    while (que.size()){
        P p = que.front(); // 从队列的最前段取出元素
        que.pop();         //取出后从队列中删除该元素
        if (p.first == gx && p.second == gy)
            break;
        //四个方向的循环
        for (int i = 0; i < 4; i++){
        //移动后的位置标记为(nx,ny)
            int nx = p.first + dx[i], ny = p.second + dy[i];
            //判断是否可以移动以及是否访问过(即d[nx][ny]!=INF）
            if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] != 'X' && d[nx][ny] == INF){
                que.push(P(nx, ny));                  //可以移动，添加到队列
                d[nx][ny] = d[p.first][p.second] + 1; //到该位置的距离为到p的距离+1
            }
        }   
    }

    return d[gx][gy];
}

int main()
{
    cin >> n >> m >> k;
    int t;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> maze[i][j];
            if(maze[i][j]=='S'){
                gx[0] = i;
                gy[0] = j;
            }else if (isdigit(maze[i][j])){
                t = maze[i][j] - '0';
                gx[t] = i;
                gy[t] = j;
            }
        }
    }

    int sum = 0;
    for (int i = 1; i <= k; i++)
        sum += bfs(gx[i - 1], gy[i - 1], gx[i], gy[i]);

    cout << sum << endl;

    return 0;
}