BFS:图的最短路径  Aizu - 0558 Cheese

Cheese

大意：在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的奶酪的工厂。输出最少用时。

チーズ ()

問題

今年も JOI 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した．JOI 町は東西南北に区画整理されていて，各区画は巣，チーズ工場，障害物，空き地のいずれかである．ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる．

この町には，N 個のチーズ工場があり，どの工場も１種類のチーズだけを生産している．チーズの硬さは工場によって異なっており，硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある．

ねずみの最初の体力は 1 であり，チーズを 1 個食べるごとに体力が 1 増える．ただし，ねずみは自分の体力よりも硬いチーズを食べることはできない．

ねずみは，東西南北に隣り合う区画に 1 分で移動することができるが，障害物の区画には入ることができない．チーズ工場をチーズを食べずに通り過ぎることもできる．すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け．ただし，ねずみがチーズを食べるのにかかる時間は無視できる．

入力

入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≤ H ≤ 1000，1 ≤ W ≤ 1000，1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'，'X'，'.' からなる W 文字の文字列が書かれており，各々が各区画の状態を表している．北から i 番目，西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W)，第 i+1 行目の j 番目の文字は，区画 (i,j) が巣である場合は 'S' となり，障害物である場合は 'X' となり，空き地である場合は '.' となり，硬さ 1, 2, ..., 9 のチーズを生産する工場である場合はそれぞれ '1', '2', ..., '9' となる．入力には巣と硬さ 1, 2, ..., N のチーズを生産する工場がそれぞれ 1 つずつある．他のマスは障害物または空き地であることが保証されている．ねずみは全てのチーズを食べられることが保証されている．

出力

すべてのチーズを食べ終えるまでにかかる最短時間（分）を表す整数を 1 行で出力せよ．

入出力例

入力例 1

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

出力例 1

入力例 2

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

出力例 2

入力例 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.......

出力例 3

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<map>
#include<set>
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;
}