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

#include <queue>

#include <string>

#include <cstdio>

#include <cstring>

#include <utility>

using namespace std;

typedef pair<int, int> P;

char maze[1005][1005];

int d[1005][1005];

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

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

int h, w, n, hard; 

int si, sj;

const int INF = 0x3f3f3f3f;

int tot = 0; 



void BFS(int ai, int aj){

    queue<P> que;

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

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

            d[i][j] = INF;

        }

    }

    que.push(P(ai, aj));

    d[ai][aj] = 0;

    while(!que.empty()){

        P a = que.front();

        que.pop();

        int x = a.first, y = a.second;

        if(maze[x][y]-'0' == hard){

            tot += d[x][y];

            si = x; sj = y;

            break;

        }

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

            int dx = x+dirx[i], dy = y+diry[i];

            if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){

                d[dx][dy] = d[x][y]+1;

                que.push(P(dx, dy));

            }

        }

    }

}



int main(int argc, char const *argv[]){

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

        getchar();

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

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

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

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

                    si = i; sj = j;

                }

            }

            getchar();

        }

        tot = 0;

        hard = 1;

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

            BFS(si, sj);

            hard++;

        }

        cout << tot << 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: 5.0676548680026015x):
#include <iostream>

#include <queue>

#include <string>

#include <cstdio>

#include <cstring>

#include <utility>

using namespace std;

typedef pair<int, int> P;

char maze[1005][1005];

int d[1005][1005];

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

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

int h, w, n, hard; 

int si, sj;

const int INF = 0x3f3f3f3f;

int tot = 0; 



void BFS(int ai, int aj){

    queue<P> que;

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

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

            d[i][j] = INF;

        }

    }

    que.push(P(ai, aj));

    d[ai][aj] = 0;

    while(!que.empty()){

        P a = que.front();

        que.pop();

        int x = a.first, y = a.second;

        if(maze[x][y]-'0' == hard){

            tot += d[x][y];

            si = x; sj = y;

            break;

        }

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

            int dx = x+dirx[i], dy = y+diry[i];

            if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){

                d[dx][dy] = d[x][y]+1;

                que.push(P(dx, dy));

            }

        }

    }

}



int main(int argc, char const *argv[]){

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

        getchar();

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

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

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

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

                    si = i; sj = j;

                }

            }

            getchar();

        }

        tot = 0;

        hard = 1;

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

            BFS(si, sj);

            hard++;

        }

        cout << tot << endl;

    }

    return 0;

}
// 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: 2.255616532777491x):
#include <iostream>

#include <queue>

#include <string>

#include <cstdio>

#include <cstring>

#include <utility>

using namespace std;

typedef pair<int, int> P;

char maze[1005][1005];

int d[1005][1005];

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

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

int h, w, n, hard; 

int si, sj;

const int INF = 0x3f3f3f3f;

int tot = 0; 



void BFS(int ai, int aj){

    queue<P> que;

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

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

            d[i][j] = INF;

        }

    }

    que.push(P(ai, aj));

    d[ai][aj] = 0;

    while(!que.empty()){

        P a = que.front();

        que.pop();

        int x = a.first, y = a.second;

        if(maze[x][y]-'0' == hard){

            tot += d[x][y];

            si = x; sj = y;

            break;

        }

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

            int dx = x+dirx[i], dy = y+diry[i];

            if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){

                d[dx][dy] = d[x][y]+1;

                que.push(P(dx, dy));

            }

        }

    }

}



int main(int argc, char const *argv[]){

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

        getchar();

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

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

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

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

                    si = i; sj = j;

                }

            }

            getchar();

        }

        tot = 0;

        hard = 1;

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

            BFS(si, sj);

            hard++;

        }

        cout << tot << 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: 10.40469879288316x):
#include <iostream>

#include <queue>

#include <string>

#include <cstdio>

#include <cstring>

#include <utility>

using namespace std;

typedef pair<int, int> P;

char maze[1005][1005];

int d[1005][1005];

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

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

int h, w, n, hard; 

int si, sj;

const int INF = 0x3f3f3f3f;

int tot = 0; 



void BFS(int ai, int aj){

    queue<P> que;

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

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

            d[i][j] = INF;

        }

    }

    que.push(P(ai, aj));

    d[ai][aj] = 0;

    while(!que.empty()){

        P a = que.front();

        que.pop();

        int x = a.first, y = a.second;

        if(maze[x][y]-'0' == hard){

            tot += d[x][y];

            si = x; sj = y;

            break;

        }

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

            int dx = x+dirx[i], dy = y+diry[i];

            if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){

                d[dx][dy] = d[x][y]+1;

                que.push(P(dx, dy));

            }

        }

    }

}



int main(int argc, char const *argv[]){

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

        getchar();

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

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

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

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

                    si = i; sj = j;

                }

            }

            getchar();

        }

        tot = 0;

        hard = 1;

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

            BFS(si, sj);

            hard++;

        }

        cout << tot << endl;

    }

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

#include <queue>

#include <string>

#include <cstdio>

#include <cstring>

#include <utility>

using namespace std;

typedef pair<int, int> P;

char maze[1005][1005];

int d[1005][1005];

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

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

int h, w, n, hard; 

int si, sj;

const int INF = 0x3f3f3f3f;

int tot = 0; 



void BFS(int ai, int aj){

    queue<P> que;

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

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

            d[i][j] = INF;

        }

    }

    que.push(P(ai, aj));

    d[ai][aj] = 0;

    while(!que.empty()){

        P a = que.front();

        que.pop();

        int x = a.first, y = a.second;

        if(maze[x][y]-'0' == hard){

            tot += d[x][y];

            si = x; sj = y;

            break;

        }

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

            int dx = x+dirx[i], dy = y+diry[i];

            if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){

                d[dx][dy] = d[x][y]+1;

                que.push(P(dx, dy));

            }

        }

    }

}



int main(int argc, char const *argv[]){

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

        getchar();

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

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

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

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

                    si = i; sj = j;

                }

            }

            getchar();

        }

        tot = 0;

        hard = 1;

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

            BFS(si, sj);

            hard++;

        }

        cout << tot << 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: 6.370072428383167x):
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

int H,W,N;

char mm[1005][1005];

bool v[1005][1005];

int xx,yy;

struct node{

    int x,y,step;

};

queue<node> que;

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

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

bool check(int x,int  y){

    if(1<=x&&x<=H&&1<=y&&y<=W&&!v[x][y]&&mm[x][y]!='X')return true;

    else return false;

}

int bfs(int g){

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

    node t;

    t.x=xx;

    t.y=yy;

    t.step=0;

    v[xx][yy]=1;

    que.push(t);

    while(!que.empty()){

        t=que.front();

        que.pop();

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

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

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

            if(check(nx,ny)){

                if(mm[nx][ny]==g+'0'){

                    xx=nx;

                    yy=ny;

                    return t.step+1;

                }

                node tt;

                tt.x=nx;

                tt.y=ny;

                tt.step=t.step+1;

                v[nx][ny]=1;

                que.push(tt);

            }

        }

    }

}

int main(){

    while(~scanf("%d%d%d",&H,&W,&N)){

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

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

        }

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

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

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

                    xx=i;

                    yy=j;

                }

            }

        }

        int ans=0;

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

            memset(v,0,sizeof(v));

            ans+=bfs(i);

        }

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

#include<cstdio>

#include<queue>

#include<cstring>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

int H,W,N;

char mm[1005][1005];

bool v[1005][1005];

int xx,yy;

struct node{

    int x,y,step;

};

queue<node> que;

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

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

bool check(int x,int  y){

    if(1<=x&&x<=H&&1<=y&&y<=W&&!v[x][y]&&mm[x][y]!='X')return true;

    else return false;

}

int bfs(int g){

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

    node t;

    t.x=xx;

    t.y=yy;

    t.step=0;

    v[xx][yy]=1;

    que.push(t);

    while(!que.empty()){

        t=que.front();

        que.pop();

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

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

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

            if(check(nx,ny)){

                if(mm[nx][ny]==g+'0'){

                    xx=nx;

                    yy=ny;

                    return t.step+1;

                }

                node tt;

                tt.x=nx;

                tt.y=ny;

                tt.step=t.step+1;

                v[nx][ny]=1;

                que.push(tt);

            }

        }

    }

}

int main(){

    while(~scanf("%d%d%d",&H,&W,&N)){

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

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

        }

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

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

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

                    xx=i;

                    yy=j;

                }

            }

        }

        int ans=0;

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

            memset(v,0,sizeof(v));

            ans+=bfs(i);

        }

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

    }

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

#include<cstdio>

#include<queue>

#include<cstring>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

int H,W,N;

char mm[1005][1005];

bool v[1005][1005];

int xx,yy;

struct node{

    int x,y,step;

};

queue<node> que;

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

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

bool check(int x,int  y){

    if(1<=x&&x<=H&&1<=y&&y<=W&&!v[x][y]&&mm[x][y]!='X')return true;

    else return false;

}

int bfs(int g){

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

    node t;

    t.x=xx;

    t.y=yy;

    t.step=0;

    v[xx][yy]=1;

    que.push(t);

    while(!que.empty()){

        t=que.front();

        que.pop();

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

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

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

            if(check(nx,ny)){

                if(mm[nx][ny]==g+'0'){

                    xx=nx;

                    yy=ny;

                    return t.step+1;

                }

                node tt;

                tt.x=nx;

                tt.y=ny;

                tt.step=t.step+1;

                v[nx][ny]=1;

                que.push(tt);

            }

        }

    }

}

int main(){

    while(~scanf("%d%d%d",&H,&W,&N)){

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

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

        }

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

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

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

                    xx=i;

                    yy=j;

                }

            }

        }

        int ans=0;

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

            memset(v,0,sizeof(v));

            ans+=bfs(i);

        }

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

    }

    return 0; 

}