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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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

#include<queue>

#include<cctype>





using namespace std;



int cnt;

char field[1002][1002];

int cost[1002][1002];

int factory[9][2];

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

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



int bfs(int sx, int sy, int gx, int gy) {

    queue< pair<int,int> > que;



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

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

            cost[i][j] = -1;

        }

    }



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

    cost[sx][sy] = 0;



    while(!que.empty()) {

        pair<int, int> p;

        p = que.front();

        que.pop();

        

        if(p.first == gx && p.second == gy) {

            break;

        }



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

            int tx = p.first + x[i]; int ty = p.second + y[i];

            if(field[tx][ty] != 'X' && cost[tx][ty] == -1) {

                que.push(pair<int, int>(tx, ty));

                cost[tx][ty] = cost[p.first][p.second] + 1;

            }

        }

    }

    return cost[gx][gy];

}



int main() {

    int w, h, n, sx, sy;



    cin >> h >> w >> n;



    for (int y = 1; y <= h; y++) {

        for (int x = 1; x <= w; x++) {

            cin >> field[x][y];

            if (field[x][y] == 'S') {

                sx = x;

                sy = y;

            } else if(isdigit(field[x][y])) {

                int tmp = field[x][y] - '0';

                factory[tmp][0] = x;

                factory[tmp][1] = y;

            }

        }

        field[0][y] = 'X';

        field[w + 1][y] = 'X';

    }



    for (int x = 0; x <= w + 1; x++) {

        field[x][0] = 'X';

        field[x][h + 1] = 'X';

    }



    int cnt = 0;

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

        // 次の目的地へ行くで

        cnt += bfs(sx, sy, factory[i][0], factory[i][1]);

        sx = factory[i][0];

        sy = factory[i][1];

    }



    cout << cnt << endl;

}

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define SC(x) scanf("%d",&x);

#define pr(x)  cout << x << endl;

#define mem(arr,v) memset(arr,v,sizeof arr);

#define bug(x) cout << "#x = " << x <<endl;

const int inf = 0x3f3f3f3f;

const int maxn = 1010;

typedef long long ll;

using namespace std;

char Mz[maxn][maxn],c;

bool vis[maxn][maxn];

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

int M,N,C;

int px[10],py[10];

struct node {

	int x,y,step;

};



int bfs(int des,int sx,int sy) {

	mem(vis,0);

	vis[sx][sy] = 1;

	node nod = {sx,sy,0};

	queue<node> q;

	q.push(nod);



	while(!q.empty()) {

		nod =  q.front();

		q.pop();

		

		int x = nod.x, y = nod.y;

		int step =  nod.step;

		

		if(Mz[x][y] == des + '0')

			return step;

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

			int dx = x + dir[i][0];

			int dy = y + dir[i][1];

			if(Mz[dx][dy] == 'X' || Mz[dx][dy] == -1 || vis[dx][dy])	continue;

			nod = {dx,dy,step + 1};

			q.push(nod);

			vis[dx][dy] = 1;

		}

	}

}



int main() {

//	freopen("in.txt","r",stdin);

	cin >> N >> M >> C;

	mem(Mz,-1)

	mem(px,0)  mem(py,0)



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

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

			cin >> c;

			Mz[i][j] = c;

			if(c == '.' || c == 'X')	continue;

			if(c == 'S') px[0] = i, py[0] = j;

			else

				px[c - '0'] = i , py[c - '0'] = j;

		}

	int res = 0;

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

		if(px[i] && py[i]) {

//				dfs(i + 1,px[i],py[i],0);

			res += bfs(i + 1,px[i],py[i]);

		}

	}

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

}

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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

#include<cstring>

#include<queue>

using namespace std;

int map[1005][1005];

struct node{

	int x,y,time;

}s[10],p;

queue<node> q;

int vis[1005][1005];

int n,m,T;

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

int bfs(int a,int b){

	while(!q.empty())

		q.pop();

	q.push(s[a]);

	memset(vis,0,sizeof vis);

	vis[s[a].x][s[a].y]=1;

	while(!q.empty()){

		p=q.front();

		q.pop();

		int x=p.x,y=p.y,time=p.time;

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

			int x1=x+dir[i][0],y1=y+dir[i][1];

			if(x1<=0||y1<=0||x1>n||y1>m||vis[x1][y1]||map[x1][y1])

				continue ;

			if(x1==s[b].x&&y1==s[b].y)

				return time+1;

			vis[x1][y1]=1;

			p.x=x1,p.y=y1,p.time=time+1;

			q.push(p);

		}

	}

}

int main()

{

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

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

		scanf("\n");

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

			char c;

			c=getchar();

			if(c=='S')

				s[0].x=i,s[0].y=j;

			if(c=='X')

				map[i][j]=1;

			if(c>='1'&&c<='9')

				s[c-'0'].x=i,s[c-'0'].y=j;

		}

	}

	int time=0;

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

		time+=bfs(i,i+1);

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

}

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

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



struct Node{

	int x,y;

};



const int max_n=1000+10;

int h,w,n,dx[]={0,0,-1,1},dy[]={-1,1,0,0},d[max_n][max_n],ans;

Node sN;

char c[max_n][max_n];



void bfs(int m){

	if(m>n)return;

	queue<Node> q;

	memset(d,0,sizeof(d));

	q.push(sN);

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

	while(!q.empty()){

		Node p=q.front();

		q.pop();

		

		if(c[p.x][p.y]=='0'+m){

		    ans+=d[p.x][p.y]-1;

		    sN.x=p.x;

		    sN.y=p.y;

		    return;

		}

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

			Node nN;

			nN.x=p.x+dx[i];

			nN.y=p.y+dy[i];

			if(nN.x>=0 && nN.x<h 

            && nN.y>=0 && nN.y<w 

		   	&& c[nN.x][nN.y]!='X' && !d[nN.x][nN.y]){

				q.push(nN);

				d[nN.x][nN.y]=d[p.x][p.y]+1;

			}

		}

	}

}



int main(){

    scanf("%d%d%d",&h,&w,&n);

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

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

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

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

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

            	sN.x=i;

            	sN.y=j;

            	break;

            }

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

    cout<<ans<<endl;

    return 0;

}

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

#include <queue>

#include <string>

using namespace std;

int main()

{

	int h,w,n;

	int sx,sy;

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

	string map[1001];

	int d[1001][1001];

	int x = 0;

	cin >> h >> w >> n;

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

	{

		cin >> map[i];

	}

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

	{

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

		{

			d[j][i] = -1;

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

			{

				sx = j;

				sy = i;

			}

		}

	}

	d[sx][sy] = 0;

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

	{

		queue< pair<int, int> > que;

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

		{

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

			{

				d[k][j] = -1;

			}

		}

		d[sx][sy] = 0;

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

		while(que.size())

		{

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

			que.pop();

			if((map[p.second][p.first] - '0') == (i+1))

			{

				sx = p.first;

				sy = p.second;

				x+=d[sx][sy];

				break;

			}

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

			{

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

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

				if(0 <= nx && nx < w && 0 <= ny && ny < h && map[ny][nx] != 'X' && d[nx][ny] == -1)

				{

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

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

				}

			}

		}

	}

	cout << x << endl;

}
// 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.3660830591766593x):


#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>



using namespace std;

const int maxn = 1e3 + 5;

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

int mp[maxn][maxn];

//bool vis[maxn][maxn];

int d[maxn][maxn];

struct point{

    int x,y;

};

int h,w,n;

 int dis = 0;

void bfs(point &p,int cnt)

{

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

    memset(d, 0, sizeof(d));

    queue<point> q;

    q.push(p);

    while (!q.empty()) {

        point t = q.front();q.pop();

        //vis[t.x][t.y] = true;

        if(mp[t.x][t.y] == cnt + 1) {dis += d[t.x][t.y];p.x = t.x,p.y = t.y;return ;}

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

            int tx = t.x + dir[i][0];

            int ty = t.y + dir[i][1];

            if (tx >= 0 && tx < h && ty >= 0 && ty < w && !d[tx][ty] && mp[tx][ty] != -1) {

                q.push({tx,ty});

                d[tx][ty] = 1 + d[t.x][t.y];

            }

        }

    }

}

int main()

{

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

        getchar();

        char ch;

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

       // int sx,sy;

        point s;

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

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

                scanf("%c",&ch);

                if(ch == 'S') {s.x = i,s.y = j;mp[i][j] = 0;}

                else if(ch == '.') {mp[i][j] = 0;}

                else if(isdigit(ch)) {mp[i][j] = ch - '0';}

            }

            getchar();

        }

       

        dis = 0;

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

            bfs(s,i);

        }

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

    }

    return 0;

}