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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

	return 0;

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

using namespace std;

const int MAX = 1024;



int h, w, n, maze[MAX][MAX];

int b[15];

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

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

int d[MAX][MAX];

int ans = 0;



int readchar() {

    for(;;) {

        int ch = getchar();

        if(ch != '\n' && ch != '\r') return ch;

    }

}



int bfs(int x, int y, int x2, int y2)

{

    //cout << x << y << x2 << y2 << endl;



    queue<int> q;

    q.push(x * 10000 + y);

    while(!q.empty()) {

        int v = q.front();

        q.pop();

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

            int x1 = v / 10000 + r[i];

            int y1 = v % 10000 + z[i];

            if(x1 == x2 && y1 == y2) {

                d[x1][y1] = d[v / 10000][v % 10000] + 1;

                return 0;

            }

            if(x1 >= 0 && y1 >= 0 && x1 < h && y1 < w && maze[x1][y1] != 'X' && d[x1][y1] == -1) {

                 d[x1][y1] = d[v / 10000][v % 10000] + 1;

                 q.push(x1 * 10000 + y1);

            }

        }

    }

    return 0;

}

int main()

{

    cin >> h >> w >> n;

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

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

             maze[i][j] = readchar();

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

            b[0] = i * 10000 + j;

        }

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

            b[maze[i][j] - '0'] = i * 10000 + j;

        }

    }

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

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

        d[b[i] / 10000][b[i] % 10000] = 0;

        bfs(b[i] / 10000, b[i] % 10000, b[i + 1] / 10000, b[i + 1] % 10000);

        ans += d[b[i + 1] / 10000][ b[i + 1] % 10000];

    }

    cout << ans << endl;

    return 0;

}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

	return 0;

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

#include<string.h>

#include<algorithm>

#include<queue>



using namespace std;



struct node

{

    int s;

    int x,y;

};



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

int vis[1010][1010];

int n,m,k,sx[20],sy[20];

char mp[1010][1010];



int bfs(int x,int y,int ex,int ey)

{

    queue<node> q;

    node a,b,d;

    a.x = x;

    a.y = y;

    a.s = 0;

    vis[x][y] = 1;

    q.push(a);

    while(!q.empty())

    {

        b = q.front();

        q.pop();

        if(b.x == ex && b.y == ey)

        {

            return b.s;

        }

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

        {

            d.x = b.x + dir[i][0];

            d.y = b.y + dir[i][1];

            if(d.x >= 0 && d.x < n && d.y >= 0 && d.y < m && vis[d.x][d.y] == 0)

            {

                if(mp[d.x][d.y] >= '1' && mp[d.x][d.y] <= '9' || mp[d.x][d.y] == '.')

                {

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

                    d.s = b.s + 1;

                    q.push(d);

                }

            }

        }

    }

}



int main()

{

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

    {

        int i,j,t;



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

        {

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

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

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

                {

                    sx[0] = i;

                    sy[0] = j;

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

                }

        }

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

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

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

                {

                    sx[mp[i][j]-'0'] = i;

                    sy[mp[i][j]-'0'] = j;

                }

        int ans = 0;

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

        {

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

            ans += bfs(sx[i-1],sy[i-1],sx[i],sy[i]);

        }

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

    }

    return 0;

}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

	return 0;

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

#include<string.h>

#include<algorithm>

#include<queue>



using namespace std;



struct node

{

    int s;

    int x,y;

};



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

int vis[1010][1010];

int n,m,k,sx[20],sy[20];



char map[1010][1010];



int bfs(int x,int y,int ex,int ey)

{

    queue<node> q;

    node a,b,d;

    a.x = x;

    a.y = y;

    a.s = 0;

    vis[x][y] = 1;

    q.push(a);

    while(!q.empty())

    {

        b = q.front();

        q.pop();

        if(b.x == ex && b.y == ey)

           {

                return b.s;

           }

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

        {

            d.x = b.x + dir[i][0];

            d.y = b.y + dir[i][1];

            if(d.x >= 0 && d.x < n && d.y >= 0 && d.y < m && vis[d.x][d.y] == 0)

            {

                if(map[d.x][d.y] >= '1' && map[d.x][d.y] <= '9' || map[d.x][d.y] == '.')

                {

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

                    d.s = b.s + 1;

                    q.push(d);

                }

            }

        }

    }

}



int main()

{

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

    {

        int i,j,t;



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

        {

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

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

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

                {

                    sx[0] = i;

                    sy[0] = j;

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

                }

        }

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

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

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

                {

                    sx[map[i][j]-'0'] = i;

                    sy[map[i][j]-'0'] = j;

                }

        int ans = 0;

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

        {

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

            ans += bfs(sx[i-1],sy[i-1],sx[i],sy[i]);

        }

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

    }

    return 0;

}

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

#include<queue>

#include<algorithm>

using namespace std;



typedef pair<int,int> P;



const int inf=10000;

const int maxh=1010;

const int maxw=1010;

const int maxn=9;



int h,w,n;

int d[maxh][maxw];

char m[maxh][maxw];



int bx,by;

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

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



int bfs(char c){

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

		fill(d[i],d[i]+w,inf);

	}

	d[bx][by]=0;

	queue<P> que;

	que.push(P(bx,by));

	while(!que.empty()){

		P p=que.front();

		que.pop();

		if(m[p.first][p.second]==c){

			bx=p.first,by=p.second;

			break;

		}

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

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

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

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

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

				d[nx][ny]=d[p.first][p.second]+1;

			}

		}

	}

	return d[bx][by];

}



void solve(){

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

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

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

				bx=i,by=j;

				break;

			}

		}

	}

	int ans=0;

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

		ans+=bfs('0'+i);

	}

	cout<<ans<<endl;

}



int main(){

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

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

			cin>>m[i];

		}

		solve();

	}

	return 0;

}