stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

} 


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

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int MAX_N=100000;

const int INF = 0x3f3f3f3f;

int n,m,k;

char map[1010][1010];

bool vis[1010][1010];



struct p{

	int x;

	int y;

	int step;

};

int ans=0;



bool yesorno(p x){

	if(x.x<1||x.x>m||x.y<1||x.y>n||map[x.y][x.x]=='X'||vis[x.y][x.x]==1)

		return 0;

	return 1;

}



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

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

void bfs(p st,int ww){

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

	if(ww==k)

		return;

	int temp=0;

	queue<p> q;

	q.push(st);

//	cout<<st.step<<" "<<ww<<" "<<k<<endl;

	while(!q.empty()){

		

		p ne=q.front();

		q.pop();

		if(map[ne.y][ne.x]==(char)'0'+ww+1){

			ans=ne.step;

			bfs(ne,ww+1);

			return;

		}

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

			p tem=ne;

			tem.x=tem.x+sx[i];

			tem.y=tem.y+sy[i];

			tem.step++;

			if(yesorno(tem)){

				q.push(tem);

				vis[tem.y][tem.x]=1;

			}

				

		}

	}

}

int main(){

	ios::sync_with_stdio(false);

	while(cin>>n>>m>>k){

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

		p st;

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

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

				cin>>map[i][j];

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

					st.x=j;

					st.y=i;

					st.step=0;

				}

			}

		}

		bfs(st,0);

		cout<<ans<<endl;

	}





	return 0;

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

#include <string.h>  

#include <queue>  

#define MAX_W 1000  

#define MAX_H 1000  

#define MAX_N 9  

  

using namespace std;  

  

char m[MAX_H][MAX_W + 1];  

int w, h, n;  

int gx[MAX_N + 1], gy[MAX_N + 1];  

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

  

int bfs(int sx, int sy, int gx, int gy)  

{  

    int d[MAX_H][MAX_W];  

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

    queue<int> que;  

    que.push(sx * w + sy);  

    d[sx][sy] = 0;  

          

    while(que.size())  

    {  

        int x = que.front()/w, y = que.front()%w;  

        que.pop();  

        if(x == gx && y == gy)  

            break;  

  

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

            int nx = x + dx[di], ny = y + dy[di];  

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

                d[nx][ny] = d[x][y] + 1;  

                que.push(nx * w + ny);  

            }  

        }  

    }  

    return d[gx][gy];  

}  

  

void solve()  

{  

    int ans = 0;  

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

        ans += bfs(gx[i], gy[i], gx[i + 1], gy[i + 1]);  

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

}  

  

int main()  

{  

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

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

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

          

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

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

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

                gx[m[i][j] - '0'] = i, gy[m[i][j] - '0'] = j;  

            else if('S' == m[i][j])  

                gx[0] = i, gy[0] = j;  

        }  

  

    if(w || h)  

        solve();  

    return 0;  

}  


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

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int MAX_N=100000;

const int INF = 0x3f3f3f3f;

int n,m,k;

char map[1010][1010];

bool vis[1010][1010];



struct p{

	int x;

	int y;

	int step;

};

int ans=0;



bool yesorno(p x){

	if(x.x<1||x.x>m||x.y<1||x.y>n||map[x.y][x.x]=='X'||vis[x.y][x.x]==1)

		return 0;

	return 1;

}



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

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

void bfs(p st,int ww){

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

	if(ww==k)

		return;

	int temp=0;

	queue<p> q;

	q.push(st);

//	cout<<st.step<<" "<<ww<<" "<<k<<endl;

	while(!q.empty()){

		

		p ne=q.front();

		q.pop();

		if(map[ne.y][ne.x]==(char)'0'+ww+1){

			ans=ne.step;

			bfs(ne,ww+1);

			return;

		}

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

			p tem=ne;

			tem.x=tem.x+sx[i];

			tem.y=tem.y+sy[i];

			tem.step++;

			if(yesorno(tem)){

				q.push(tem);

				vis[tem.y][tem.x]=1;

			}

				

		}

	}

}

int main(){

	ios::sync_with_stdio(false);

	while(cin>>n>>m>>k){

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

		p st;

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

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

				cin>>map[i][j];

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

					st.x=j;

					st.y=i;

					st.step=0;

				}

			}

		}

		bfs(st,0);

		cout<<ans<<endl;

	}





	return 0;

}
// Slower C++ solution:
//AOJ-0558

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;



char map[1010][1010];

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

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

int vis[1010][1010];

int m, n, N;

struct node{

	int x, y, t;

};



node bfs(int x, int y, char k)

{

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

	queue<node> q;

	node s, e, p;

	s = {x, y, 0};

	q.push(s); vis[x][y] = 1;

	while(!q.empty())

	{

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

		if(map[p.x][p.y] == k) return p;

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

		{

			int nx = p.x + dx[i];

			int ny = p.y + dy[i];

			if(nx >= n || nx < 0 || ny >= m || ny < 0 || map[nx][ny] == 'X') continue;

			if(!vis[nx][ny]){

				vis[nx][ny] = 1;

				e = {nx, ny, p.t + 1};

				q.push(e);

			}	

		}

	}

}





int main()

{

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

	{

		node s;

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

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

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

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

			   	 s.x = i; s.y = j; s.t = 0;

			   }

			}	

		}

		int ans = 0;

		char c = '0';

		for(char i = 1; i <= N; i++)

		{

			node t = bfs(s.x, s.y, c + i);

			ans += t.t;

			s.x = t.x; s.y = t.y;

		}

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

	}

	return 0; 

}


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

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int MAX_N=100000;

const int INF = 0x3f3f3f3f;

int n,m,k;

char map[1010][1010];

bool vis[1010][1010];



struct p{

	int x;

	int y;

	int step;

};

int ans=0;



bool yesorno(p x){

	if(x.x<1||x.x>m||x.y<1||x.y>n||map[x.y][x.x]=='X'||vis[x.y][x.x]==1)

		return 0;

	return 1;

}



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

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

void bfs(p st,int ww){

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

	if(ww==k)

		return;

	int temp=0;

	queue<p> q;

	q.push(st);

//	cout<<st.step<<" "<<ww<<" "<<k<<endl;

	while(!q.empty()){

		

		p ne=q.front();

		q.pop();

		if(map[ne.y][ne.x]==(char)'0'+ww+1){

			ans=ne.step;

			bfs(ne,ww+1);

			return;

		}

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

			p tem=ne;

			tem.x=tem.x+sx[i];

			tem.y=tem.y+sy[i];

			tem.step++;

			if(yesorno(tem)){

				q.push(tem);

				vis[tem.y][tem.x]=1;

			}

				

		}

	}

}

int main(){

	ios::sync_with_stdio(false);

	while(cin>>n>>m>>k){

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

		p st;

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

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

				cin>>map[i][j];

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

					st.x=j;

					st.y=i;

					st.step=0;

				}

			}

		}

		bfs(st,0);

		cout<<ans<<endl;

	}





	return 0;

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

#include<algorithm>

#include<math.h>

#include<string.h>

#include<queue>

#include<stdio.h>

using namespace std;



typedef struct{

	int x,y;

}p;

char a[1005][1005];

p acm[11];

p s,g;

int b[1005][1005];

int H,W,N;

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

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

int bfs(p s,p g)

{

	queue<p> q;

	p n;

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

	q.push(s);

	b[s.x][s.y]=0;

	while(!q.empty())

	{

		p h;

		h=q.front();

		q.pop();

		if(h.x==g.x&&h.y==g.y)

		{

			break;

		}

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

		{

			n.x=h.x+dx[i];

			n.y=h.y+dy[i];

			if(n.x>=0&&n.x<H&&n.y>=0&&n.y<W&&a[n.x][n.y]!='X'&&b[n.x][n.y]==-1)

			{

				q.push(n);

				b[n.x][n.y]=b[h.x][h.y]+1;

			}

		}

	}

	return b[g.x][g.y];

}

int main()

{

	int i,j,t,step=0;

	scanf("%d%d%d",&H,&W,&N);

	for(i=0;i<H;i++)

	{

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

	}

	for(i=0;i<H;i++)

	for(j=0;j<W;j++)

	{

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

		{

			t=a[i][j]-'0';

		    acm[t].x=i;

		    acm[t].y=j;

		}

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

		{

			s.x=i;

			s.y=j;

			a[i][j]='.';

		}

	}

		for(i=1;i<=N;i++)

		{

			g.x=acm[i].x;

			g.y=acm[i].y;

			step+=bfs(s,g);

			s.x=g.x;

			s.y=g.y;

			a[g.x][g.y]='.';

		}

	

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

	return 0;

 } 


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

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int MAX_N=100000;

const int INF = 0x3f3f3f3f;

int n,m,k;

char map[1010][1010];

bool vis[1010][1010];



struct p{

	int x;

	int y;

	int step;

};

int ans=0;



bool yesorno(p x){

	if(x.x<1||x.x>m||x.y<1||x.y>n||map[x.y][x.x]=='X'||vis[x.y][x.x]==1)

		return 0;

	return 1;

}



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

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

void bfs(p st,int ww){

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

	if(ww==k)

		return;

	int temp=0;

	queue<p> q;

	q.push(st);

//	cout<<st.step<<" "<<ww<<" "<<k<<endl;

	while(!q.empty()){

		

		p ne=q.front();

		q.pop();

		if(map[ne.y][ne.x]==(char)'0'+ww+1){

			ans=ne.step;

			bfs(ne,ww+1);

			return;

		}

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

			p tem=ne;

			tem.x=tem.x+sx[i];

			tem.y=tem.y+sy[i];

			tem.step++;

			if(yesorno(tem)){

				q.push(tem);

				vis[tem.y][tem.x]=1;

			}

				

		}

	}

}

int main(){

	ios::sync_with_stdio(false);

	while(cin>>n>>m>>k){

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

		p st;

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

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

				cin>>map[i][j];

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

					st.x=j;

					st.y=i;

					st.step=0;

				}

			}

		}

		bfs(st,0);

		cout<<ans<<endl;

	}





	return 0;

}
// 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: 1.223867478370519x):
#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <vector>

#include <queue>

using namespace std;

int n,m,p;

int sx,sy;

char s[1505][1505];

struct node{

	int x,y,step;

	node(int sx,int sy,int step)

	{

		this->x=sx;this->y=sy;this->step=step;

	}

};

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

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

int vis[1505][1500];

node bfs(node u,int pos)

{

	queue<node> q;

	while(!q.empty())q.pop();

	q.push(u);

	

	while(!q.empty())

	{

		node v=q.front();q.pop();

		if(s[v.x][v.y]==pos+'0') return v;

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

		{

			int x=v.x+dx[i];

			int y=v.y+dy[i];

			if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='X'&&vis[x][y]==0)

			{

				vis[x][y]=1;

				node now=node(x,y,v.step+1);

				q.push(now);

			}

		}

	}

}

int main()

{

	while(cin>>n>>m>>p)

	{

		int ans=0;

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

		{

			cin>>s[i]+1;

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

			{

				if(s[i][j]=='S') sx=i,sy=j;

			}

		}

		node u=node(sx,sy,0);	

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

		{		

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

			vis[u.x][u.y]=1;

			u=bfs(u,i);

			ans+=u.step;

			u.step=0;

		}

		cout<<ans<<endl;

	}

	return 0;

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

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <vector>

#include <queue>

using namespace std;

int n,m,p;

int sx,sy;

char s[1505][1505];

struct node{

	int x,y,step;

	node(int sx,int sy,int step)

	{

		this->x=sx;this->y=sy;this->step=step;

	}

};

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

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

int vis[1505][1500];

node bfs(node u,int pos)

{

	queue<node> q;

	while(!q.empty())q.pop();

	q.push(u);

	

	while(!q.empty())

	{

		node v=q.front();q.pop();

		if(s[v.x][v.y]==pos+'0') return v;

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

		{

			int x=v.x+dx[i];

			int y=v.y+dy[i];

			if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='X'&&vis[x][y]==0)

			{

				vis[x][y]=1;

				node now=node(x,y,v.step+1);

				q.push(now);

			}

		}

	}

}

int main()

{

	while(cin>>n>>m>>p)

	{

		int ans=0;

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

		{

			cin>>s[i]+1;

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

			{

				if(s[i][j]=='S') sx=i,sy=j;

			}

		}

		node u=node(sx,sy,0);	

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

		{		

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

			vis[u.x][u.y]=1;

			u=bfs(u,i);

			ans+=u.step;

			u.step=0;

		}

		cout<<ans<<endl;

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.046265529594847x):


#include<iostream>

#include<queue>

#include<string.h>

using namespace std;

char map[1005][1005];

char map1[1005][1005];

int a[1005][1005];

int m,n,q,num=0;

int main()

{

	int x,y;

	cin>>m>>n>>q;

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

	{

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

		{

			cin>>map[i][j];

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

				{

					x=i;

					y=j;

				 map[x][y]='0';

				}

		}

	}

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

		{

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

			{

				map1[i][j]=map[i][j];



			}

		}



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

	{

			queue<int> ac;

			queue<int> ak;



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

		{

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

			{

				map[i][j]=map1[i][j];

				if(map1[i][j]-'0'==k-1)

				{

					x=i;

					y=j;

					map[x][y]='X';

				}

			}

		}

		memset(a,0,sizeof(a));

		ac.push(x);

		ak.push(y);

		while(!ac.empty())

		{

			x=ac.front();

			y=ak.front();

			ac.pop();

			ak.pop();

			if(x+1<m)

			{

				if(map[x+1][y]!='X')

				{

					if(map[x+1][y]-'0'==k)

					{

						num+=a[x][y];

						num+=1;

						break;

					}

						map[x+1][y]='X';

						ac.push(x+1);

						ak.push(y);

						a[x+1][y]=a[x][y]+1;

				}

			}

				if(x-1>=0)

				{

					if(map[x-1][y]!='X')

					{



						if(map[x-1][y]-'0'==k)

						{

							num+=a[x][y]+1;

							break;

						}

						map[x-1][y]='X';

						ac.push(x-1);

						ak.push(y);

						a[x-1][y]=a[x][y]+1;

					}

				}

			if(y+1<n)

			{

				if(map[x][y+1]!='X')

				{



					if(map[x][y+1]-'0'==k)

					{

						num+=a[x][y]+1;

						break;

					}



						map[x][y+1]='X';

						ac.push(x);

						ak.push(y+1);

						a[x][y+1]=a[x][y]+1;

				}

			}

			if(y-1>=0)

			{

				if(map[x][y-1]!='X')

				{



					if(map[x][y-1]-'0'==k)

					{

						num+=a[x][y]+1;

						break;

					}



						map[x][y-1]='X';

						ac.push(x);

						ak.push(y-1);

						a[x][y-1]=a[x][y]+1;

				}

			}

		}

	}

	cout<<num<<endl;

	return 0;

}
// 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.5499223737016834x):
#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  

{  

    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';  

                }  

            }  

        }  

        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;  

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

#include <cstring>

#include <iostream>

using namespace std;



const int N = 1111;

const int cx[] = {0, 0, 1, -1}, cy[] = {1, -1, 0, 0};

char maze[N][N];

int step[N][N];

int h, w, n, sx, sy, ans;



int bfs(int cheese){

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

    queue<pair<int, int> > que;

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

    step[sx][sy] = 0;

    while(!que.empty()){

        int x = que.front().first, y = que.front().second;

        que.pop();

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

            int nx = x + cx[i], ny = y + cy[i];

            if(nx < 0 || h <= nx || ny < 0 || w <= ny || maze[nx][ny] == 'X' || step[nx][ny] != -1) continue;

            step[nx][ny] = step[x][y] + 1;

            if(maze[nx][ny] - '0' == cheese){

                sx = nx;

                sy = ny;

                return step[nx][ny];

            }

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

        }

    }

    return 0;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    while(cin >> h >> w >> n){

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

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

                cin >> maze[i][j];

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

                    sx = i;

                    sy = j;

                }

            }

        ans = 0;

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

            ans += bfs(i);

        cout << ans << endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2117366380687469x):
#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  

{  

    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';  

                }  

            }  

        }  

        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;  

}