stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int map[1005][1005];

struct node{

	int x,y,time;

}s[10],p;

queue<node> q;

int vis[1005][1005];

int n,m,T;

int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int bfs(int a,int b){

	while(!q.empty())

		q.pop();

	q.push(s[a]);

	memset(vis,0,sizeof vis);

	vis[s[a].x][s[a].y]=1;

	while(!q.empty()){

		p=q.front();

		q.pop();

		int x=p.x,y=p.y,time=p.time;

		for(int i=0;i<4;i++){

			int x1=x+dir[i][0],y1=y+dir[i][1];

			if(x1<=0||y1<=0||x1>n||y1>m||vis[x1][y1]||map[x1][y1])

				continue ;

			if(x1==s[b].x&&y1==s[b].y)

				return time+1;

			vis[x1][y1]=1;

			p.x=x1,p.y=y1,p.time=time+1;

			q.push(p);

		}

	}

}

int main()

{

	scanf("%d%d%d",&n,&m,&T);

	for(int i=1;i<=n;i++){

		scanf("\n");

		for(int j=1;j<=m;j++){

			char c;

			c=getchar();

			if(c=='S')

				s[0].x=i,s[0].y=j;

			if(c=='X')

				map[i][j]=1;

			if(c>='1'&&c<='9')

				s[c-'0'].x=i,s[c-'0'].y=j;

		}

	}

	int time=0;

	for(int i=0;i<T;i++)

		time+=bfs(i,i+1);

	printf("%d\n",time);

}

// Faster C++ solution for the same problem (measured speedup: 4.9327922076151065x):
#include<iostream>

#include<iomanip>

#include<math.h>

#include<vector>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<time.h>

#define INF 1000000000ll

#define MOD 1000000007ll

#define EPS 1e-10

#define REP(i,m) for(long long i=0; i<m; i++)

#define FOR(i,n,m) for(long long i=n; i<m; i++)

#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }

#define ALL(v) v.begin(),v.end()

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef long double ld;



/*

 貪欲

 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B

 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか

 ?

 */



/*

 DP

 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)

 */



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);

	ll h,w,n;

	cin>>h>>w>>n;

	vector<vector<char>> m(h,vector<char>(w));

	REP(i,h) REP(j,w) cin>>m[i][j];

	ll ret=0;

	REP(i,n) {

		vector<vector<ll>> dir(h,vector<ll>(w,INF));

		queue<P> q;

		REP(j,h) REP(k,w) {

			if(i==0) {

				if(m[j][k]=='S') {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			} else {

				if(m[j][k]=='0'+i) {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			}

		}

		while(!q.empty()) {

			P p=q.front();

			q.pop();

			ll dx[]={1,0,-1,0};

			ll dy[]={0,1,0,-1};

			REP(j,4) {

				ll nx=p.first+dx[j];

				ll ny=p.second+dy[j];

				if(nx>=0&&nx<h&&ny>=0&&ny<w&&m[nx][ny]!='X'&&dir[nx][ny]==INF) {

					q.push(P(nx,ny));

					dir[nx][ny]=dir[p.first][p.second]+1;

				}

			}

		}

		REP(j,h) REP(k,w) {

			if(m[j][k]=='1'+i) ret+=dir[j][k];

		}

	}

	cout<<ret<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <stack>

#include <utility>

#include <algorithm>

#include <sstream>

using namespace std;

typedef pair<int,int> P;



const int max_n=1000+10;

int h,w,n,sx,sy,dx[]={0,0,-1,1},dy[]={-1,1,0,0},d[max_n][max_n],ans;

char c[max_n][max_n];



void bfs(int x,int y,int m){

	if(m>n)return;

	queue<P> q;

	memset(d,0,sizeof(d));

	q.push(P(x,y));

	d[x][y]=1;

	while(!q.empty()){

		P p=q.front();

		q.pop();

		if(c[p.first][p.second]=='0'+m){

		    ans+=d[p.first][p.second]-1;

		    bfs(p.first,p.second,m+1);

		    return;

		}

		for(int i=0;i<4;i++){

			int tx=p.first+dx[i],ty=p.second+dy[i];

			if(tx>=0 && tx<h && ty>=0 && ty<w && c[tx][ty]!='X' && !d[tx][ty]){

				q.push(P(tx,ty));

				d[tx][ty]=d[p.first][p.second]+1;

			}

		}

	}

}



int main(){

    scanf("%d%d%d",&h,&w,&n);

    for(int i=0;i<h;i++)

        for(int j=0;j<w;j++){

            cin>>c[i][j];

            if(c[i][j]=='S'){sx=i;sy=j;}

        }

    bfs(sx,sy,1);

    cout<<ans<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.0614377969068505x):
#include<iostream>

#include<iomanip>

#include<math.h>

#include<vector>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<time.h>

#define INF 1000000000ll

#define MOD 1000000007ll

#define EPS 1e-10

#define REP(i,m) for(long long i=0; i<m; i++)

#define FOR(i,n,m) for(long long i=n; i<m; i++)

#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }

#define ALL(v) v.begin(),v.end()

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef long double ld;



/*

 貪欲

 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B

 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか

 ?

 */



/*

 DP

 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)

 */



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);

	ll h,w,n;

	cin>>h>>w>>n;

	vector<vector<char>> m(h,vector<char>(w));

	REP(i,h) REP(j,w) cin>>m[i][j];

	ll ret=0;

	REP(i,n) {

		vector<vector<ll>> dir(h,vector<ll>(w,INF));

		queue<P> q;

		REP(j,h) REP(k,w) {

			if(i==0) {

				if(m[j][k]=='S') {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			} else {

				if(m[j][k]=='0'+i) {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			}

		}

		while(!q.empty()) {

			P p=q.front();

			q.pop();

			ll dx[]={1,0,-1,0};

			ll dy[]={0,1,0,-1};

			REP(j,4) {

				ll nx=p.first+dx[j];

				ll ny=p.second+dy[j];

				if(nx>=0&&nx<h&&ny>=0&&ny<w&&m[nx][ny]!='X'&&dir[nx][ny]==INF) {

					q.push(P(nx,ny));

					dir[nx][ny]=dir[p.first][p.second]+1;

				}

			}

		}

		REP(j,h) REP(k,w) {

			if(m[j][k]=='1'+i) ret+=dir[j][k];

		}

	}

	cout<<ret<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <stack>

#include <utility>

#include <algorithm>

#include <sstream>

using namespace std;



struct Node{

	int x,y;

};



const int max_n=1000+10;

int h,w,n,dx[]={0,0,-1,1},dy[]={-1,1,0,0},d[max_n][max_n],ans;

Node sN;

char c[max_n][max_n];



void bfs(int m){

	if(m>n)return;

	queue<Node> q;

	memset(d,0,sizeof(d));

	q.push(sN);

	d[sN.x][sN.y]=1;

	while(!q.empty()){

		Node p=q.front();

		q.pop();

		

		if(c[p.x][p.y]=='0'+m){

		    ans+=d[p.x][p.y]-1;

		    sN.x=p.x;

		    sN.y=p.y;

		    return;

		}

		for(int i=0;i<4;i++){

			Node nN;

			nN.x=p.x+dx[i];

			nN.y=p.y+dy[i];

			if(nN.x>=0 && nN.x<h 

            && nN.y>=0 && nN.y<w 

		   	&& c[nN.x][nN.y]!='X' && !d[nN.x][nN.y]){

				q.push(nN);

				d[nN.x][nN.y]=d[p.x][p.y]+1;

			}

		}

	}

}



int main(){

    scanf("%d%d%d",&h,&w,&n);

    for(int i=0;i<h;i++)

        scanf("%s",c[i]);

    for(int i=0;i<h;i++)

        for(int j=0;j<w;j++)

            if(c[i][j]=='S'){

            	sN.x=i;

            	sN.y=j;

            	break;

            }

    for(int i=1;i<=n;i++)bfs(i);

    cout<<ans<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.05884817188019x):
#include<iostream>

#include<iomanip>

#include<math.h>

#include<vector>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<time.h>

#define INF 1000000000ll

#define MOD 1000000007ll

#define EPS 1e-10

#define REP(i,m) for(long long i=0; i<m; i++)

#define FOR(i,n,m) for(long long i=n; i<m; i++)

#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }

#define ALL(v) v.begin(),v.end()

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef long double ld;



/*

 貪欲

 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B

 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか

 ?

 */



/*

 DP

 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)

 */



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);

	ll h,w,n;

	cin>>h>>w>>n;

	vector<vector<char>> m(h,vector<char>(w));

	REP(i,h) REP(j,w) cin>>m[i][j];

	ll ret=0;

	REP(i,n) {

		vector<vector<ll>> dir(h,vector<ll>(w,INF));

		queue<P> q;

		REP(j,h) REP(k,w) {

			if(i==0) {

				if(m[j][k]=='S') {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			} else {

				if(m[j][k]=='0'+i) {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			}

		}

		while(!q.empty()) {

			P p=q.front();

			q.pop();

			ll dx[]={1,0,-1,0};

			ll dy[]={0,1,0,-1};

			REP(j,4) {

				ll nx=p.first+dx[j];

				ll ny=p.second+dy[j];

				if(nx>=0&&nx<h&&ny>=0&&ny<w&&m[nx][ny]!='X'&&dir[nx][ny]==INF) {

					q.push(P(nx,ny));

					dir[nx][ny]=dir[p.first][p.second]+1;

				}

			}

		}

		REP(j,h) REP(k,w) {

			if(m[j][k]=='1'+i) ret+=dir[j][k];

		}

	}

	cout<<ret<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

	int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

	for(int i=0;i < h;i++)

	{

		cin >> map[i];

	}

	for(int i=0;i < h;i++)

	{

		for(int j=0;j < w;j++)

		{

			d[j][i] = -1;

			if(map[i][j] == 'S')

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

	for(int i=0;i<9;i++)

	{

		queue< pair<int, int> > que;

		for(int j=0;j < h;j++)

		{

			for(int k=0;k < w;k++)

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

		que.push(make_pair(sx,sy));

		while(que.size())

		{

			pair<int, int> p = que.front();

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

			for(int j=0;j < 4;j++)

			{

				int nx = p.first + dx[j];

				int ny = p.second + dy[j];

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

					que.push(make_pair(nx,ny));

					d[nx][ny] = d[p.first][p.second] + 1;

				}

			}

		}

	}

	cout << x << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1189719284101638x):
#include<iostream>

#include<iomanip>

#include<math.h>

#include<vector>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<time.h>

#define INF 1000000000ll

#define MOD 1000000007ll

#define EPS 1e-10

#define REP(i,m) for(long long i=0; i<m; i++)

#define FOR(i,n,m) for(long long i=n; i<m; i++)

#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }

#define ALL(v) v.begin(),v.end()

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef long double ld;



/*

 貪欲

 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B

 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか

 ?

 */



/*

 DP

 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)

 */



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);

	ll h,w,n;

	cin>>h>>w>>n;

	vector<vector<char>> m(h,vector<char>(w));

	REP(i,h) REP(j,w) cin>>m[i][j];

	ll ret=0;

	REP(i,n) {

		vector<vector<ll>> dir(h,vector<ll>(w,INF));

		queue<P> q;

		REP(j,h) REP(k,w) {

			if(i==0) {

				if(m[j][k]=='S') {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			} else {

				if(m[j][k]=='0'+i) {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			}

		}

		while(!q.empty()) {

			P p=q.front();

			q.pop();

			ll dx[]={1,0,-1,0};

			ll dy[]={0,1,0,-1};

			REP(j,4) {

				ll nx=p.first+dx[j];

				ll ny=p.second+dy[j];

				if(nx>=0&&nx<h&&ny>=0&&ny<w&&m[nx][ny]!='X'&&dir[nx][ny]==INF) {

					q.push(P(nx,ny));

					dir[nx][ny]=dir[p.first][p.second]+1;

				}

			}

		}

		REP(j,h) REP(k,w) {

			if(m[j][k]=='1'+i) ret+=dir[j][k];

		}

	}

	cout<<ret<<endl;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

const int maxn=1005;

int n,m,k,dx[]={-1,1,0,0},dy[]={0,0,1,-1},vis[maxn][maxn];

char map[maxn][maxn];

struct maze

{

    maze(int xx=0,int yy=0,int tt=0):x(xx),y(yy),time(tt){}

	int x,y,time;

};

maze bfs(int bx,int by,char ch)

{

	memset(vis,0,sizeof(vis));

	queue<maze> q;

	maze st(bx,by,0);

	q.push(st);vis[bx][by]=1;

	while(!q.empty())

	{

		st=q.front();q.pop();

		if(map[st.x][st.y]==ch)

		{

			return st;

		}

		for(int i=0;i<4;++i)

		{

			int tx=st.x+dx[i],ty=st.y+dy[i];

			if(tx<0||tx>=n||ty<0||ty>=m||map[tx][ty]=='X')//越界和?

			{

				continue;

			}

			maze tp(tx,ty,st.time+1);

			if(!vis[tx][ty])

			{

				vis[tx][ty]=1;

				q.push(tp);

			}

		}

	}

}

int main()

{



	while(~scanf("%d%d%d",&n,&m,&k))

	{

		int bx,by;

		for(int i=0;i<n;++i)

		{

			scanf("%s",map[i]);

			for(int j=0;j<m;++j)

			{

				if(map[i][j]=='S')

				{

					bx=i;by=j;

					

					map[i][j]='0'; //第0个起点

				}

			}

		}

		int ans=0;

		for(int i=0;i<k;++i)

		{

			maze tp=bfs(bx,by,map[bx][by]+1);

			ans+=tp.time;

			bx=tp.x;by=tp.y;

		}

		printf("%d\n",ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.928562895841709x):
#include<iostream>

#include<iomanip>

#include<math.h>

#include<vector>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<time.h>

#define INF 1000000000ll

#define MOD 1000000007ll

#define EPS 1e-10

#define REP(i,m) for(long long i=0; i<m; i++)

#define FOR(i,n,m) for(long long i=n; i<m; i++)

#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }

#define ALL(v) v.begin(),v.end()

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef long double ld;



/*

 貪欲

 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B

 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか

 ?

 */



/*

 DP

 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)

 */



int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);

	ll h,w,n;

	cin>>h>>w>>n;

	vector<vector<char>> m(h,vector<char>(w));

	REP(i,h) REP(j,w) cin>>m[i][j];

	ll ret=0;

	REP(i,n) {

		vector<vector<ll>> dir(h,vector<ll>(w,INF));

		queue<P> q;

		REP(j,h) REP(k,w) {

			if(i==0) {

				if(m[j][k]=='S') {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			} else {

				if(m[j][k]=='0'+i) {

					dir[j][k]=0;

					q.push(P(j,k));

				}

			}

		}

		while(!q.empty()) {

			P p=q.front();

			q.pop();

			ll dx[]={1,0,-1,0};

			ll dy[]={0,1,0,-1};

			REP(j,4) {

				ll nx=p.first+dx[j];

				ll ny=p.second+dy[j];

				if(nx>=0&&nx<h&&ny>=0&&ny<w&&m[nx][ny]!='X'&&dir[nx][ny]==INF) {

					q.push(P(nx,ny));

					dir[nx][ny]=dir[p.first][p.second]+1;

				}

			}

		}

		REP(j,h) REP(k,w) {

			if(m[j][k]=='1'+i) ret+=dir[j][k];

		}

	}

	cout<<ret<<endl;

}
// Slower C++ solution:
/*

*

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#define CLR(ARR,NUM) memset(ARR,NUM,sizeof(ARR))

#define GETNUM(NUM) scanf("%d",&NUM)

#define faster_io() ios_base::sync_with_stdio(false)

using namespace std;

const int MAXN = 1010;

char map[MAXN][MAXN];

bool vis[10][MAXN][MAXN];

struct node{

	int x;

	int y;

	int deep;

	int n;

};

int dx[]={0,0,1,-1};

int dy[]={1,-1,0,0};



int main()

{

	CLR(vis,false);

	CLR(map,'X');

	int h,w,n;

	cin >> h >> w >> n;

	getchar();

	int sx,sy;

	for(int i=1;i<=h;i++){

		for(int j=1;j<=w;j++){

			map[i][j]=getchar();

			if(map[i][j]=='S'){

				sx=i;

				sy=j;

			}

		}

		getchar();

	}

	node t;

	t.x=sx;

	t.y=sy;

	t.deep=0;

	t.n=0;

	queue<node>q;

	vis[0][sx][sy]=true;

	q.push(t);

	int ans = -1;

	while(!q.empty()){

		node cur=q.front();

		if(cur.n==n){

			ans=cur.deep;

			break;

		}

		q.pop();

		for(int i=0;i<4;i++){

			int tx=cur.x+dx[i];

			int ty=cur.y+dy[i];

			if(map[tx][ty]!='X'&&!vis[cur.n][tx][ty]){

				node t = cur;

				t.x=tx;

				t.y=ty;

				t.deep++;

				if(map[tx][ty]=='1'+t.n){

					t.n++;

				}

				vis[t.n][tx][ty]=true;

				q.push(t);

			}

		}

	}

	cout << ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.0468880185849x):
#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

int n,m,k,step[1010][1010],temp[1010][3];

char a[1010][1010];

int dx[]={-1,1,0,0},dy[]={0,0,-1,1};

bool vis[1010][1010];

typedef pair<int,int> P;

int bfs(int x,int y,int ex,int ey)

{

	memset(vis,true,sizeof(vis));

	memset(step,0,sizeof(step));

	queue <P> que;

	que.push(P(x,y));

	vis[x][y]=false;

	while(!que.empty())

	{

		P tmp=que.front();que.pop();

		int b=que.size();

		if(tmp.first==ex&&tmp.second==ey)

		  return step[tmp.first][tmp.second];

		for(int i=0;i<4;i++)

		{

			int tx=tmp.first+dx[i];

			int ty=tmp.second+dy[i];

			if(tx>0&&tx<=n&&ty>0&&ty<=m&&vis[tx][ty]==true&&a[tx][ty]!='X')

			{

				que.push(P(tx,ty));

				vis[tx][ty]=false;

				step[tx][ty]=step[tmp.first][tmp.second]+1;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(false);

	cin>>n>>m>>k;

		int sx,sy;

		for(int i=1;i<=n;i++)

		  for(int j=1;j<=m;j++)

		  {

			cin>>a[i][j];

			if(a[i][j]=='S')

			  sx=i,sy=j;

			//temp[0][0]=i;

			//temp[0][1]=j;

		  }

		a[sx][sy]='0';

		int tot=0,ans=0;

		for(int i=1;i<=k;i++)

		{

			for(int j=1;j<=n;j++)

			  for(int l=1;l<=m;l++)

			    if(a[j][l]=='0'+i)

			    {

			    	tot=bfs(sx,sy,j,l);

			    	sx=j,sy=l;

				}

			ans+=tot;

		}

		cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:


#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>



using namespace std;

const int maxn = 1e3 + 5;

const int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

int mp[maxn][maxn];

//bool vis[maxn][maxn];

int d[maxn][maxn];

struct point{

    int x,y;

};

int h,w,n;

 int dis = 0;

void bfs(point &p,int cnt)

{

   // memset(vis, 0, sizeof(vis));

    memset(d, 0, sizeof(d));

    queue<point> q;

    q.push(p);

    while (!q.empty()) {

        point t = q.front();q.pop();

        //vis[t.x][t.y] = true;

        if(mp[t.x][t.y] == cnt + 1) {dis += d[t.x][t.y];p.x = t.x,p.y = t.y;return ;}

        for (int i = 0; i < 4; i ++) {

            int tx = t.x + dir[i][0];

            int ty = t.y + dir[i][1];

            if (tx >= 0 && tx < h && ty >= 0 && ty < w && !d[tx][ty] && mp[tx][ty] != -1) {

                q.push({tx,ty});

                d[tx][ty] = 1 + d[t.x][t.y];

            }

        }

    }

}

int main()

{

    while (scanf("%d%d%d",&h,&w,&n) != EOF) {

        getchar();

        char ch;

        memset(mp, -1, sizeof(mp));

       // int sx,sy;

        point s;

        for (int i = 0; i < h; i ++) {

            for (int j = 0; j < w; j ++) {

                scanf("%c",&ch);

                if(ch == 'S') {s.x = i,s.y = j;mp[i][j] = 0;}

                else if(ch == '.') {mp[i][j] = 0;}

                else if(isdigit(ch)) {mp[i][j] = ch - '0';}

            }

            getchar();

        }

       

        dis = 0;

        for (int i = 0; i < n; i ++) {

            bfs(s,i);

        }

        printf("%d\n",dis);

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4983627860948392x):
#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

int n,m,k,step[1010][1010],temp[1010][3];

char a[1010][1010];

int dx[]={-1,1,0,0},dy[]={0,0,-1,1};

bool vis[1010][1010];

typedef pair<int,int> P;

int bfs(int x,int y,int ex,int ey)

{

	memset(vis,true,sizeof(vis));

	memset(step,0,sizeof(step));

	queue <P> que;

	que.push(P(x,y));

	vis[x][y]=false;

	while(!que.empty())

	{

		P tmp=que.front();que.pop();

		int b=que.size();

		if(tmp.first==ex&&tmp.second==ey)

		  return step[tmp.first][tmp.second];

		for(int i=0;i<4;i++)

		{

			int tx=tmp.first+dx[i];

			int ty=tmp.second+dy[i];

			if(tx>0&&tx<=n&&ty>0&&ty<=m&&vis[tx][ty]==true&&a[tx][ty]!='X')

			{

				que.push(P(tx,ty));

				vis[tx][ty]=false;

				step[tx][ty]=step[tmp.first][tmp.second]+1;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(false);

	cin>>n>>m>>k;

		int sx,sy;

		for(int i=1;i<=n;i++)

		  for(int j=1;j<=m;j++)

		  {

			cin>>a[i][j];

			if(a[i][j]=='S')

			  sx=i,sy=j;

			//temp[0][0]=i;

			//temp[0][1]=j;

		  }

		a[sx][sy]='0';

		int tot=0,ans=0;

		for(int i=1;i<=k;i++)

		{

			for(int j=1;j<=n;j++)

			  for(int l=1;l<=m;l++)

			    if(a[j][l]=='0'+i)

			    {

			    	tot=bfs(sx,sy,j,l);

			    	sx=j,sy=l;

				}

			ans+=tot;

		}

		cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#include"algorithm"

#include"queue"

using namespace std;

struct mmm

{

	int x,y;

}vv;

int dir[4][2] = {0,-1,-1,0,0,1,1,0};

char xx[1005][1005];

int bb[11][2];

queue <mmm> qq;

int vis[1005][1005];

int bfs(char t)

{

	int sum = 0;

	int pl = 0;

	while(!qq.empty())

	{

		vv = qq.front();

		int x0 = vv.x;

		int y0 = vv.y;

		//printf("%d %d %d\n",x0,y0,vis[x0][y0]);

		qq.pop();

		if(xx[x0][y0] == t && !pl)

		{

			sum = vis[x0][y0];

			pl = 1;

		}

		for(int i = 0;i < 4;i++)

		{

			int xt = x0 + dir[i][0];

			int yt = y0 + dir[i][1];

			if(xx[xt][yt] != '#' && xx[xt][yt] != 'X' && vis[xt][yt] == -1)

			{

				vis[xt][yt] = vis[x0][y0] + 1;

				vv.x = xt;

				vv.y = yt;

				qq.push(vv);

			}

		}

	}

	return sum;

}

int main()

{

	int a,b,c,d,x1,y1,sum;

	while(~scanf("%d %d %d",&a,&b,&c))

	{

	//	if(a == 0 && b == 0)

	//	break;

		memset(xx,'#',sizeof(xx));

		getchar();

		for(int i = 1;i <= a;i++)

		{

			for(int j = 1;j <= b;j++)

			{

				xx[i][j] = getchar();

				if(xx[i][j] == 'S')

				{

					x1 = i;

					y1 = j;

				}

				else if(xx[i][j] != 'X')

				{

					bb[xx[i][j] - '0'][0] = i;

					bb[xx[i][j] - '0'][1] = j;

				}

			}

			getchar();

		}

		bb[0][0] = x1;

		bb[0][1] = y1;

		sum = 0;

		for(int i = 1;i <= c;i++)

		{

			vv.x = bb[i-1][0];

			vv.y = bb[i-1][1];

			memset(vis,-1,sizeof(vis));

			vis[vv.x][vv.y] = 0;

			qq.push(vv);

			sum += bfs(i + '0');

		}

		printf("%d\n",sum);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.172004936309072x):
#include "cstring"

#include "cstdio"

#include "queue"

using namespace std;



const int maxn=1024;



int dx[4]={0,0,1,-1};

int dy[4]={1,-1,0,0};



char mp[maxn][maxn];

int vis[maxn][maxn];

int wx[10],wy[10];

int n,m,k;



int bfs(int x1,int y1,int x2,int y2)

{

	memset(vis,0,sizeof(vis));

	queue<int>qx;qx.push(x1);

	queue<int>qy;qy.push(y1);

	queue<int>qt;qt.push(0);

	vis[x1][y1]=1;

	

	while(!qx.empty())

	{

		int nx=qx.front();qx.pop();

		int ny=qy.front();qy.pop();

		int nt=qt.front();qt.pop();

		

		if(nx==x2 && ny==y2)return nt;

		

		for(int i=0;i<4;i++)

		{

			int px=nx+dx[i];

			int py=ny+dy[i];

			if(px>=0 && py>=0 && px<n && py<m && mp[px][py]!='X' && !vis[px][py])

			{

				qx.push(px);

				qy.push(py);

				qt.push(nt+1);

				vis[px][py]=1;

			}

		}

		

	}

	

	return 0;

}



int main()

{

	//freopen("f.txt","r",stdin);

	scanf("%d%d%d",&n,&m,&k);

	for(int i=0;i<n;i++)

		for(int j=0;j<m;j++)

		{

			mp[i][j]=getchar();

			while(mp[i][j]=='\n' || mp[i][j]=='\0')mp[i][j]=getchar();

			if(mp[i][j]>='1' && mp[i][j]<='9')

			{

				wx[mp[i][j]-'0']=i;

				wy[mp[i][j]-'0']=j;

			}

			if(mp[i][j]=='S')

			{

				wx[0]=i;

				wy[0]=j;

			}	

		}

	int ans=0;

	for(int i=0;i<k;i++)

		ans+=bfs(wx[i],wy[i],wx[i+1],wy[i+1]);

	printf("%d\n",ans);

	return 0;

}