Cheese

问题

今年JOI镇乳酪厂也开始生产奶酪，老鼠走出窝了。JOI町被划分成东西南北，各区是巢、芝士厂、障碍物或空地。老鼠从窝里出来，到所有的奶酪工厂，每人吃一个奶酪。

这个镇上，有N个奶酪厂，每个厂都只生产一种奶酪。奶酪的硬度因工厂而异，硬度从1到N的奶酪生产厂家正好各有一个。

老鼠的第一个体力是一个，每吃一个奶酪就增加一个体力。不过，老鼠吃不到比自己体力还硬的奶酪。

老鼠，一分钟就能移动到东西南北相邻的地段，不过不可能进入障碍物区。奶酪工厂不吃奶酪也能路过。写一个寻找最短时间吃完所有奶酪的程序。不过，老鼠吃奶酪的时间是可以忽视的。

输入

输入为H+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

3,1

s . .

...

. .1

输出实例1

4

输入实例2

4,5 2

. x . .1

……x

. xx . s

. 2 . x。

输出实例2

12

输入实例3

10 10 9

. x…x . s . x

6 . .5 x . .x1x

... xxxx . .x

x . .9 x…x。

8 . x2x . .x3x

... xx .×4 . .

xx……7 x . .

x . .x . .xx . .

x…x.xx . .

. .x……

输出实例3

91

分N层循环就可以了

#include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<vector>
#include<cstring>
#define MAX 1100
#define INF 10000000

using namespace std;

 

int H, W, N;
int ans;
int d[MAX][MAX];
int gl[MAX][2];
char fac[MAX][MAX];
typedef pair <int, int> P;

void Bfs(int n){
	typedef pair <int, int> P;
	queue <P> que;
	int sx = gl[n][0];
	int sy = gl[n][1];
	int gx = gl[n+1][0];
	int gy = gl[n+1][1];
	int xi[4] = {-1,1,0,0};
	int yi[4] = {0,0,-1,1};
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++){
			d[i][j] = INF;
		}		
			
	//将起点加入队列//记录距离
	que.push(P(sx, sy));
	d[sx][sy] = 0;	
	//队列不为空一直遍历
	while(!que.empty()){
		P p = que.front();
		que.pop();
		if(p.first==gx && p.second==gy)break;
		//四向遍历，加队列 
		for(int i=0; i<4; i++){
			int x = p.first + xi[i];
			int y = p.second + yi[i];
			//在迷宫内，可以经过，第一次经过 
			if(x>=0 && y>=0 && x<H && y<W && fac[x][y]!='X' && d[x][y]==INF){
				d[x][y] = d[p.first][p.second]+1;
				que.push(P(x, y));
			}
		} 
	}
}

int main(){
	cin >> H >> W >> N;
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++){
			cin >> fac[i][j];
			if(fac[i][j] == 'S'){
				gl[0][0] = i;
				gl[0][1] = j;
			}
			if((int)fac[i][j]-48>=1 && (int)fac[i][j]-48<=N){
				gl[(int)fac[i][j]-48][0] = i;
				gl[(int)fac[i][j]-48][1] = j;
			}
		}	
	ans = 0;
	//分为N个循环，终点为起点，寻找下一个终点
	for(int i=0; i<N; i++){
		memset(d, INF, sizeof(d));
		Bfs(i);
		ans+=d[gl[i+1][0]][gl[i+1][1]];
	}
	cout << ans << endl;;
	return 0;
}