stablegradients/pie-gem5-pairs huggingface dataset:
// 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: 2.554218547269264x):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int r,c,n;

int ans;

char map[1005][1005];

bool book[1005][1005];

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

struct point

{

    int x,y;

    int step;

}p[11],now,last;

bool check(int x,int y)

{

    if(x<0||x>=r||y<0||y>=c)

        return 0;

    return 1;

}

void bfs(int st)

{

    p[st].step=0;

    queue<point> q;

    now=p[st];

    q.push(now);

    book[now.x][now.y]=1;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

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

        {

            last.x=now.x+dir[i][0];

            last.y=now.y+dir[i][1];

            last.step=now.step+1;

            if(!check(last.x,last.y))    continue;

            if(map[last.x][last.y]=='X'|| book[last.x][last.y]==1)    continue;

            if(last.x==p[st+1].x && last.y==p[st+1].y)

            {

                ans+=last.step;

                return;

            }

            book[last.x][last.y]=1;

            q.push(last);

        }

    }

}

int main()

{

    while(~scanf("%d%d%d",&r,&c,&n))

    {

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

        {

            getchar();

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

            {

                scanf("%c",&map[i][j]);

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

                {

                    p[0].x=i;

                    p[0].y=j;

                }

                if(map[i][j]!='S'&&map[i][j]!='X'&&map[i][j]!='.')

                {

                    p[map[i][j]-'0'].x=i;

                    p[map[i][j]-'0'].y=j;

                }

            }

        }

        ans=0;

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

        {

            memset(book,0,sizeof(book));

            bfs(i);

        }

        cout<<ans<<endl;

    }

    //system("pause");

    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

{

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

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int r,c,n;

int ans;

char map[1005][1005];

bool book[1005][1005];

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

struct point

{

    int x,y;

    int step;

}p[11],now,last;

bool check(int x,int y)

{

    if(x<0||x>=r||y<0||y>=c)

        return 0;

    return 1;

}

void bfs(int st)

{

    p[st].step=0;

    queue<point> q;

    now=p[st];

    q.push(now);

    book[now.x][now.y]=1;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

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

        {

            last.x=now.x+dir[i][0];

            last.y=now.y+dir[i][1];

            last.step=now.step+1;

            if(!check(last.x,last.y))    continue;

            if(map[last.x][last.y]=='X'|| book[last.x][last.y]==1)    continue;

            if(last.x==p[st+1].x && last.y==p[st+1].y)

            {

                ans+=last.step;

                return;

            }

            book[last.x][last.y]=1;

            q.push(last);

        }

    }

}

int main()

{

    while(~scanf("%d%d%d",&r,&c,&n))

    {

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

        {

            getchar();

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

            {

                scanf("%c",&map[i][j]);

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

                {

                    p[0].x=i;

                    p[0].y=j;

                }

                if(map[i][j]!='S'&&map[i][j]!='X'&&map[i][j]!='.')

                {

                    p[map[i][j]-'0'].x=i;

                    p[map[i][j]-'0'].y=j;

                }

            }

        }

        ans=0;

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

        {

            memset(book,0,sizeof(book));

            bfs(i);

        }

        cout<<ans<<endl;

    }

    //system("pause");

    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: 2.684050080641041x):
#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:
/************************************************

* Author        :somniloquy

* Created Time  :2015/10/30 16:15:09

 ************************************************/



#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <queue>



using namespace std;



const int hw_max = 1000 + 5;

char graph[hw_max][hw_max];

int sign[hw_max][hw_max];

int h, w, n, ans;

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

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

struct node

{

	int x;

	int y;

	int time;

} start;



void BFS(node op, char ed)

{

	queue <node> process;

	process.push(op);

	sign[op.x][op.y] = 1;

	while(!process.empty())

	{

		node now = process.front();

		process.pop();

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

		{

			node next = now;

			next.x += dx[i];

			next.y += dy[i];

			next.time ++;

			if(next.x >= 0 && next.x < h && next.y >= 0 && next.y < w && graph[next.x][next.y] != 'X' && !sign[next.x][next.y])

			{

				if(graph[next.x][next.y] == ed)

				{

					ans += next.time;

					next.time = 0;

					start = next;

				       	return;

				}

				else

				{

					process.push(next);

					sign[next.x][next.y] = 1;

				}

			}

		}

	}

}



int main()

{

	while(~scanf("%d %d %d", & h, & w, & n))

	{

		getchar();

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

		{

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

			{

			       scanf("%c", & graph[i][j]);

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

			       {

					start.x = i;

					start.y = j;

					start.time = 0;

			       }

			}

			getchar();

		}

		ans = 0;

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

		{

			memset(sign, 0, sizeof(sign));

			BFS(start, '0' + i);

		}

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

	}

	return 0;

}

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

#include<queue>

#include<utility>

#include<cstring>

using namespace std;

char map[1005][1005];

bool vis[1005][1005];

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

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

int sx,sy;

int h,w;

int bfs(int n){

	memset(vis,false,sizeof(vis));

	queue<pair<pair<int,int>,int> >que;

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

	while(!que.empty()){

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

		int cnt=que.front().second;

		que.pop();

		if(map[now.first][now.second]==n+48){

			sx=now.first;

			sy=now.second;

			return cnt;

		}

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

			int _x=now.first+dx[i];

			int _y=now.second+dy[i];

			if(_x<0||_y<0||_x>=h||_y>=w||map[_x][_y]=='X'||vis[_x][_y]){

				continue;

			}

			vis[_x][_y]=true;

			que.push(make_pair(make_pair(_x,_y),cnt+1));

		}

	}

}

int main(){

	int n;

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

		memset(map,0,sizeof(map));

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

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

		}

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

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

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

					sx=i;

					sy=j;

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

					break;

				}

			}

		}

		int count=0;

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

			count+=bfs(k);

		}

		cout<<count<<endl;

	}

	return 0;

}

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

}