stablegradients/pie-gem5-pairs huggingface dataset:
// 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.1904678354337928x):


#include<iostream>

#include<cstdio>

#include<deque>

#include<algorithm>



using namespace std;



const int maxn=1e3+5;

const int inf=0x3f3f3f3f;



typedef pair<int,int>P;



int h,w,n,sx,sy,book[maxn][maxn],goal[10],Next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char s[maxn][maxn];



int judge(int row,int col)

{

    if(row>=0&&row<h&&col>=0&&col<w){

        return 1;

    }

    return 0;

}



int bfs()

{

    int res=0;

    deque<P>q;

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

        fill(book[0],book[0]+maxn*maxn,inf);

        q.push_back(P(sx,sy));

        book[sx][sy]=0;

        while(!q.empty()){

            int x=q.front().first;

            int y=q.front().second;

            q.pop_front();

            if((int)s[x][y]==49+ci){

                goal[ci]=book[x][y];

                sx=x;

                sy=y;

                break;

            }

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

                int nx=x+Next[i][0];

                int ny=y+Next[i][1];

                if(judge(nx,ny)&&s[nx][ny]!='X'&&book[nx][ny]==inf){

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

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

                }

            }

        }

        q.clear();

        res+=goal[ci];

    }

    return res;

}



int main()

{

    cin>>h>>w>>n;

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

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

            cin>>s[i][j];

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

                sx=i;

                sy=j;

            }

        }

    }

    int res=bfs();

    cout<<res<<endl;

    return 0;

}
// Slower C++ solution:
#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;

}

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


#include<iostream>

#include<cstdio>

#include<deque>

#include<algorithm>



using namespace std;



const int maxn=1e3+5;

const int inf=0x3f3f3f3f;



typedef pair<int,int>P;



int h,w,n,sx,sy,book[maxn][maxn],goal[10],Next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char s[maxn][maxn];



int judge(int row,int col)

{

    if(row>=0&&row<h&&col>=0&&col<w){

        return 1;

    }

    return 0;

}



int bfs()

{

    int res=0;

    deque<P>q;

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

        fill(book[0],book[0]+maxn*maxn,inf);

        q.push_back(P(sx,sy));

        book[sx][sy]=0;

        while(!q.empty()){

            int x=q.front().first;

            int y=q.front().second;

            q.pop_front();

            if((int)s[x][y]==49+ci){

                goal[ci]=book[x][y];

                sx=x;

                sy=y;

                break;

            }

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

                int nx=x+Next[i][0];

                int ny=y+Next[i][1];

                if(judge(nx,ny)&&s[nx][ny]!='X'&&book[nx][ny]==inf){

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

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

                }

            }

        }

        q.clear();

        res+=goal[ci];

    }

    return res;

}



int main()

{

    cin>>h>>w>>n;

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

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

            cin>>s[i][j];

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

                sx=i;

                sy=j;

            }

        }

    }

    int res=bfs();

    cout<<res<<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.0469252891202614x):


#include<iostream>

#include<cstdio>

#include<deque>

#include<algorithm>



using namespace std;



const int maxn=1e3+5;

const int inf=0x3f3f3f3f;



typedef pair<int,int>P;



int h,w,n,sx,sy,book[maxn][maxn],goal[10],Next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char s[maxn][maxn];



int judge(int row,int col)

{

    if(row>=0&&row<h&&col>=0&&col<w){

        return 1;

    }

    return 0;

}



int bfs()

{

    int res=0;

    deque<P>q;

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

        fill(book[0],book[0]+maxn*maxn,inf);

        q.push_back(P(sx,sy));

        book[sx][sy]=0;

        while(!q.empty()){

            int x=q.front().first;

            int y=q.front().second;

            q.pop_front();

            if((int)s[x][y]==49+ci){

                goal[ci]=book[x][y];

                sx=x;

                sy=y;

                break;

            }

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

                int nx=x+Next[i][0];

                int ny=y+Next[i][1];

                if(judge(nx,ny)&&s[nx][ny]!='X'&&book[nx][ny]==inf){

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

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

                }

            }

        }

        q.clear();

        res+=goal[ci];

    }

    return res;

}



int main()

{

    cin>>h>>w>>n;

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

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

            cin>>s[i][j];

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

                sx=i;

                sy=j;

            }

        }

    }

    int res=bfs();

    cout<<res<<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.7876928869846263x):
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int>P;

const int Max_n=1100;



int n,m,d;

struct Node{

    int x,y,d;

    Node(int xx,int yy,int dd):x(xx),y(yy),d(dd){}

};

char s[Max_n][Max_n];

bool vis[Max_n][Max_n];

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

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



Node bfs(int x1,int y1,int k){

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

    queue<Node>que;

    que.push(Node(x1,y1,0));

    vis[x1][y1]=1;

    while(!que.empty()){

        Node node=que.front();que.pop();

        int x=node.x,y=node.y;

        if(k==s[x][y]-'0')return node;

        int d=node.d;

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

            int X=x+dx[i],Y=y+dy[i];

            if(!vis[X][Y]&&(s[X][Y]=='S'||s[X][Y]=='.'||(s[X][Y]>='1'&&s[X][Y]<='9'))){

                vis[X][Y]=1;

                que.push(Node(X,Y,d+1));

            }

        }

    }

}



int main()

{

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

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

        int x,y;

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

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

            if(s[i][j]=='S'){x=i;y=j;}

        }

        int sum=0;

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

            Node node=bfs(x,y,i);

            sum+=node.d;

            x=node.x,y=node.y;

        }

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

    }

    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: 3.7601133308709436x):
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int>P;

const int Max_n=1100;



int n,m,d;

struct Node{

    int x,y,d;

    Node(int xx,int yy,int dd):x(xx),y(yy),d(dd){}

};

char s[Max_n][Max_n];

bool vis[Max_n][Max_n];

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

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



Node bfs(int x1,int y1,int k){

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

    queue<Node>que;

    que.push(Node(x1,y1,0));

    vis[x1][y1]=1;

    while(!que.empty()){

        Node node=que.front();que.pop();

        int x=node.x,y=node.y;

        if(k==s[x][y]-'0')return node;

        int d=node.d;

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

            int X=x+dx[i],Y=y+dy[i];

            if(!vis[X][Y]&&(s[X][Y]=='S'||s[X][Y]=='.'||(s[X][Y]>='1'&&s[X][Y]<='9'))){

                vis[X][Y]=1;

                que.push(Node(X,Y,d+1));

            }

        }

    }

}



int main()

{

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

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

        int x,y;

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

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

            if(s[i][j]=='S'){x=i;y=j;}

        }

        int sum=0;

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

            Node node=bfs(x,y,i);

            sum+=node.d;

            x=node.x,y=node.y;

        }

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

    }

    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.7868258003841786x):
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int>P;

const int Max_n=1100;



int n,m,d;

struct Node{

    int x,y,d;

    Node(int xx,int yy,int dd):x(xx),y(yy),d(dd){}

};

char s[Max_n][Max_n];

bool vis[Max_n][Max_n];

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

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



Node bfs(int x1,int y1,int k){

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

    queue<Node>que;

    que.push(Node(x1,y1,0));

    vis[x1][y1]=1;

    while(!que.empty()){

        Node node=que.front();que.pop();

        int x=node.x,y=node.y;

        if(k==s[x][y]-'0')return node;

        int d=node.d;

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

            int X=x+dx[i],Y=y+dy[i];

            if(!vis[X][Y]&&(s[X][Y]=='S'||s[X][Y]=='.'||(s[X][Y]>='1'&&s[X][Y]<='9'))){

                vis[X][Y]=1;

                que.push(Node(X,Y,d+1));

            }

        }

    }

}



int main()

{

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

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

        int x,y;

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

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

            if(s[i][j]=='S'){x=i;y=j;}

        }

        int sum=0;

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

            Node node=bfs(x,y,i);

            sum+=node.d;

            x=node.x,y=node.y;

        }

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

    }

    return 0;

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

#include <queue>

#include <string.h>

using namespace std;

typedef pair<int, int> P;

int sx,sy,H,W,N;

char map1[1002][1002];

int step[1002][1002];

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

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

void find1(int g){

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

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

        if(map1[i][k] == 'S' || map1[i][k] == (g+48)){

        if(map1[i][k] == 'S') map1[i][k] ='.';

        sx = i; sy = k;

        return ;

    }

}



int bfs(int n)

{

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

    queue <P> que;

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

    step[sx][sy] = 0;

    while(que.size()){

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

        que.pop();

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

            int xn = x + dx[i], yn = y + dy[i];

            if(xn >= 0 && xn < W && yn >= 0 && yn < H && map1[xn][yn] != 'X' && step[xn][yn] == -1)

                {

                    step[xn][yn] = step[x][y] + 1;

                    if(map1[xn][yn] == (n+48))

                        {

                            return step[xn][yn];

                        }

                    que.push(P(xn, yn));

                }

        }

    }

return 0;

}



int main()

{

    cin >> W >> H >> N;

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

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

        cin >> map1[i][k];

    int step = 0;

    find1(0);

    step += bfs(1);

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

    {



        find1(i);

        step += bfs(i+1);

    }

    cout << step << endl;

    return 0;

}

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

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int>P;

const int Max_n=1100;



int n,m,d;

struct Node{

    int x,y,d;

    Node(int xx,int yy,int dd):x(xx),y(yy),d(dd){}

};

char s[Max_n][Max_n];

bool vis[Max_n][Max_n];

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

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



Node bfs(int x1,int y1,int k){

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

    queue<Node>que;

    que.push(Node(x1,y1,0));

    vis[x1][y1]=1;

    while(!que.empty()){

        Node node=que.front();que.pop();

        int x=node.x,y=node.y;

        if(k==s[x][y]-'0')return node;

        int d=node.d;

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

            int X=x+dx[i],Y=y+dy[i];

            if(!vis[X][Y]&&(s[X][Y]=='S'||s[X][Y]=='.'||(s[X][Y]>='1'&&s[X][Y]<='9'))){

                vis[X][Y]=1;

                que.push(Node(X,Y,d+1));

            }

        }

    }

}



int main()

{

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

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

        int x,y;

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

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

            if(s[i][j]=='S'){x=i;y=j;}

        }

        int sum=0;

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

            Node node=bfs(x,y,i);

            sum+=node.d;

            x=node.x,y=node.y;

        }

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

    }

    return 0;

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

#include<string.h>

#include<queue>

#include<algorithm>

#define MAX_N 1002

using namespace std;

struct node{int x,y;};

char _map[MAX_N][MAX_N];

int dp[MAX_N][MAX_N];

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

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

int S_x,S_y;

int h,w,cnt;



node make_node(int x,int y){

	node t;

	t.x=x,t.y=y;

	return t;

}

void solve(){

	queue<node> que;

	int step=0;

	

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

		que.push(make_node(S_x,S_y));

		_map[S_x][S_y]='.';

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

		dp[S_x][S_y]=step;

		while(!que.empty()){

			node t=que.front();que.pop();

			if(_map[t.x][t.y]=='0'+i){

				step=dp[t.x][t.y];

				S_x=t.x,S_y=t.y;

				break;

			}

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

				int x=t.x+ox[j];

				int y=t.y+oy[j];

				if(0<=x&&x<h&&0<=y&&y<w&&_map[x][y]!='X'&&dp[x][y]==-1){

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

					dp[x][y]=dp[t.x][t.y]+1;

				}

			}

		}

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

	}

	

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

}



int main()

{

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

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

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

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

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

				if(_map[j][k]=='S')

					S_x=j,S_y=k,j=h,k=w;

		solve();

	}

	return 0;

}

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

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int>P;

const int Max_n=1100;



int n,m,d;

struct Node{

    int x,y,d;

    Node(int xx,int yy,int dd):x(xx),y(yy),d(dd){}

};

char s[Max_n][Max_n];

bool vis[Max_n][Max_n];

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

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



Node bfs(int x1,int y1,int k){

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

    queue<Node>que;

    que.push(Node(x1,y1,0));

    vis[x1][y1]=1;

    while(!que.empty()){

        Node node=que.front();que.pop();

        int x=node.x,y=node.y;

        if(k==s[x][y]-'0')return node;

        int d=node.d;

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

            int X=x+dx[i],Y=y+dy[i];

            if(!vis[X][Y]&&(s[X][Y]=='S'||s[X][Y]=='.'||(s[X][Y]>='1'&&s[X][Y]<='9'))){

                vis[X][Y]=1;

                que.push(Node(X,Y,d+1));

            }

        }

    }

}



int main()

{

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

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

        int x,y;

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

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

            if(s[i][j]=='S'){x=i;y=j;}

        }

        int sum=0;

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

            Node node=bfs(x,y,i);

            sum+=node.d;

            x=node.x,y=node.y;

        }

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

    }

    return 0;

}