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

}






// Faster C++ solution for the same problem (measured speedup: 1.1748749797924964x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	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: 5.419458541112535x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	return 0;

}//
// 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  

{  

    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;  

}


// Faster C++ solution for the same problem (measured speedup: 2.601137637463207x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	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: 2.5883191344581014x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	return 0;

}//
// Slower C++ solution:


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

}




// Faster C++ solution for the same problem (measured speedup: 2.6476093533642056x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	return 0;

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

}






// Faster C++ solution for the same problem (measured speedup: 1.7639625392111942x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	return 0;

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

#include<vector>

#include<queue>

#include<string.h>

#include<iostream>

#include<algorithm>

#define INF 1000000000

#define MAXN 100005

using namespace std;

int mmin=11;

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

int a[1005][1005];int m,n,k,sx,sy;

struct node{

    int x,y,cost;

};

int bfs(int x,int y,int s)

{

    queue<node>q;

    bool vis[1005][1005]={0};

    node now={x,y,0};

    q.push(now);

    while(!q.empty())

    {

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

        if(a[now.x][now.y]==s)break;

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

        {

            int xx=now.x+step[i][0],yy=now.y+step[i][1];

            if(!vis[xx][yy]&&a[xx][yy]!=-1){

                vis[xx][yy]=1;

                node temp={xx,yy,now.cost+1};

                q.push(temp);



            }

        }

    }

    //cout<<now.cost<<endl;

    sx=now.x;sy=now.y;

    return now.cost;

}

int main()

{

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

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

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

        string x;cin>>x;

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

        {

            char c=x[j-1];

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

            else if(c=='X')a[i][j]=-1;

            else if(c=='.')a[i][j]=0;

            else a[i][j]=c-'0';

        }

    }

    int sum=0;

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

    {

        sum+=bfs(sx,sy,i);

    }

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

}




// Faster C++ solution for the same problem (measured speedup: 3.1907152153468488x):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}

};

int r,c,n;

int goal[10][2];

bool vis[MAXN+5][MAXN+5];

char maz[MAXN+5][MAXN+5];

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

	que.push(QUEUE(beg[0],beg[1],0));

	while(!que.empty())

	{

		QUEUE pre=que.front();que.pop();

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

		{

			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;

			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;

			vis[X][Y]=true;

			if(X==goal[cnt][0] && Y==goal[cnt][1])

				return depth;

			que.push(QUEUE(X,Y,depth));

		}

	}

	return -1;

}

int main(){

	scanf("%d%d%d",&r,&c,&n);

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

	{

		scanf("%s",maz[i]+1);

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

		{

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

				goal[maz[i][j]-'0'][0]=i,

				goal[maz[i][j]-'0'][1]=j,

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

		ans+=BFS(goal[i-1],i);

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

	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.372401530469925x):
#include <cstdio>

#include <cmath>

#include <algorithm>

#include <queue>

#include <iostream>

#include <vector>

#include <cstdlib>

#include <cstring>

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

using namespace std;



char map[1005][1005];

int dis[1005][1005];

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

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

int row,col,n;

int current = 1;

int firstX,firstY;

int ans = 0;

typedef pair<int,int> pos;

queue <pos> q;



void bfs(){

    while(q.size()){

        pos t = q.front();

        q.pop();

        if(map[t.first][t.second] - '0'== current){

            ans += dis[t.first][t.second];

            current++;

            //清空队列保证下次起点正常

            while(q.size()){

                q.pop();

            }

            //重置距离数组

            memset(dis,INF,sizeof dis);

            dis[t.first][t.second] = 0;

            //设置下一次广搜的起点

            q.push(pos(t.first,t.second));

        }

        //四个方向进行bfs

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

            int x = t.first + dx[i];

            int y = t.second + dy[i];

            if(x<0 || x>= row || y < 0|| y>=col || map[x][y] == 'X' || dis[x][y] != INF)//INF判断是否走过

                continue;

            else{

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

                dis[x][y] = dis[t.first][t.second] + 1;

            }

        }

    }

}



int main(){

    cin>>row>>col>>n;

    //初始化

    ans = 0;

    memset(dis,INF,sizeof dis);

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

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

            cin>>map[i][j];

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

                //设置起点

                q.push(pos(i,j));

                dis[i][j] = 0;

            }

        }

    }

    //开始广搜

    bfs();

    cout<<ans<<endl;

    return 0;

}