stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<stdio.h>

#include<vector>

#include<queue>

#include<string.h>

#include<iostream>

#include<algorithm>

#define INF 1000000000

#define MAXN 100005

using namespace std;

int mmin=11;

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

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

struct node{

    int x,y,cost;

};

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

{

    queue<node>q;

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

    node now={x,y,0};

    q.push(now);

    while(!q.empty())

    {

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

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

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

        {

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

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

                vis[xx][yy]=1;

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

                q.push(temp);



            }

        }

    }

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

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

    return now.cost;

}

int main()

{

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

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

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

        string x;cin>>x;

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

        {

            char c=x[j-1];

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

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

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

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

        }

    }

    int sum=0;

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

    {

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

    }

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

}




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

#include <queue>



using namespace std;



char mp[1005][1005];

int vis[1005][1005];

int w, h, n;



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

int ans = 0, sx, sy;

int blood = 1;



struct Node{

	int x,y;

	Node(int _x, int _y){

		x = _x, y = _y;

	}

}; 

typedef struct Node Node; 



queue<Node> que;



void bfs(char t){

//	cout<<"sx = "<<sx<<", sy = "<<sy<<endl;

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

	ans = 0;

	bool flag = true;

	while(!que.empty()){

//		cout<<"ans = "<<ans<<"n = "<<n<<endl;

		int size = que.size();

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

			Node node = que.front();

			que.pop();

			int x = node.x, y = node.y;

//			cout<<"x = "<<x<<", y = "<<y<<endl;

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

				int tx = x + dirs[i][0], ty = y + dirs[i][1];

				if(tx >= 0 && tx < h && ty >= 0 && ty < w && vis[tx][ty] == 0 && mp[tx][ty] == t){

					sx = tx, sy = ty;

					ans++;

					flag = false;

					return;

				}else if(tx >= 0 && tx < h && ty >= 0 && ty < w && vis[tx][ty] == 0 &&  mp[tx][ty] != 'X'){

//					cout<<"tx = "<<tx<<", ty = "<<ty<<endl;

					que.push(Node(tx, ty));

					vis[tx][ty] = 1;

				}

			} 

		}

		ans++;

	}

	if(flag) ans = 0;

}



int main(){

	cin>>h>>w>>n;

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

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

	}

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

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

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

				sx = i, sy = j;

			}

		}

	}

	int res = 0;

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

		bfs(i + '0');

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

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

				vis[m][k] = 0;

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

		res += ans;

	}

	cout<<res<<endl;

	return 0;

}



/**

331

S..

...

..1

*/
// Slower C++ solution:
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=1000;

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

struct QUEUE{

	int x,y,dep;

	QUEUE(){}

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

};

int r,c,n;

int goal[10][2];

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

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

int BFS(int *beg,int cnt){

	memset(vis,false,sizeof vis);

	queue<QUEUE> que;

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

	while(!que.empty())

	{

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

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

		{

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

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

			vis[X][Y]=true;

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

				return depth;

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

		}

	}

	return -1;

}

int main(){

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

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

	{

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

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

		{

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

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

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

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

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

				goal[0][0]=i,

				goal[0][1]=j,

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

		}

	}

	int ans=0;

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

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

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

	return 0;

}//


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

#include <queue>



using namespace std;



char mp[1005][1005];

int vis[1005][1005];

int w, h, n;



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

int ans = 0, sx, sy;

int blood = 1;



struct Node{

	int x,y;

	Node(int _x, int _y){

		x = _x, y = _y;

	}

}; 

typedef struct Node Node; 



queue<Node> que;



void bfs(char t){

//	cout<<"sx = "<<sx<<", sy = "<<sy<<endl;

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

	ans = 0;

	bool flag = true;

	while(!que.empty()){

//		cout<<"ans = "<<ans<<"n = "<<n<<endl;

		int size = que.size();

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

			Node node = que.front();

			que.pop();

			int x = node.x, y = node.y;

//			cout<<"x = "<<x<<", y = "<<y<<endl;

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

				int tx = x + dirs[i][0], ty = y + dirs[i][1];

				if(tx >= 0 && tx < h && ty >= 0 && ty < w && vis[tx][ty] == 0 && mp[tx][ty] == t){

					sx = tx, sy = ty;

					ans++;

					flag = false;

					return;

				}else if(tx >= 0 && tx < h && ty >= 0 && ty < w && vis[tx][ty] == 0 &&  mp[tx][ty] != 'X'){

//					cout<<"tx = "<<tx<<", ty = "<<ty<<endl;

					que.push(Node(tx, ty));

					vis[tx][ty] = 1;

				}

			} 

		}

		ans++;

	}

	if(flag) ans = 0;

}



int main(){

	cin>>h>>w>>n;

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

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

	}

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

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

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

				sx = i, sy = j;

			}

		}

	}

	int res = 0;

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

		bfs(i + '0');

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

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

				vis[m][k] = 0;

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

		res += ans;

	}

	cout<<res<<endl;

	return 0;

}



/**

331

S..

...

..1

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

#include<iostream>

#include<string>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

int main(){

  int i,j;

  int a[1002][1002],c[10],d[10],n,w,h,x,y,z;

  int sm=0;

  char s;

  bool b[1002][1002];

  queue<pair<pair<int,int>,int> > q;

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

  cin>>h>>w>>n;

  for(i=1;i<h+1;i++){

    for(j=1;j<w+1;j++){

      cin>>s;

      if(s!='X'){

	a[j][i]=0;

	if(0){

	}else if(s=='.'){

	}else if(s=='S'){

	  c[0]=j;

	  d[0]=i;

	}else{

	  c[s-'0']=j;

	  d[s-'0']=i;

	}

      }

    }

  }

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

    memset(b,0,sizeof(b));

    while(q.empty()==0)

      q.pop();

    q.push(make_pair(make_pair(c[i],d[i]),0));

    for(;;){

      x=q.front().first.first;

      y=q.front().first.second;

      z=q.front().second;

      q.pop();

      if(a[x][y]!=-1&&b[x][y]==0){

	if(x==c[i+1]&&y==d[i+1])

	  break;

	b[x][y]=1;

	q.push(make_pair(make_pair(x-1,y),z+1));

	q.push(make_pair(make_pair(x,y-1),z+1));

	q.push(make_pair(make_pair(x+1,y),z+1));

	q.push(make_pair(make_pair(x,y+1),z+1));

      }

    }

    sm+=z;

  }

  cout<<sm<<endl;

  return 0;

}

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

#include<iostream>

#include<string>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

int main(){

  int i,j;

  int c[10],d[10],n,w,h,x,y,z;

  int sm=0;

  char s;

  bool a[1002][1002],b[1002][1002];

  queue<pair<pair<int,int>,int> > q;

  memset(a,0,sizeof(a));

  cin>>h>>w>>n;

  for(i=1;i<h+1;i++){

    for(j=1;j<w+1;j++){

      cin>>s;

      if(s!='X'){

	a[j][i]=1;

	if(0){

	}else if(s=='.'){

	}else if(s=='S'){

	  c[0]=j;

	  d[0]=i;

	}else{

	  c[s-'0']=j;

	  d[s-'0']=i;

	}

      }

    }

  }

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

    memset(b,0,sizeof(b));

    while(q.empty()==0)

      q.pop();

    q.push(make_pair(make_pair(c[i],d[i]),0));

    for(;;){

      x=q.front().first.first;

      y=q.front().first.second;

      z=q.front().second;

      q.pop();

      if(a[x][y]&&b[x][y]==0){

	if(x==c[i+1]&&y==d[i+1])

	  break;

	b[x][y]=1;

	q.push(make_pair(make_pair(x-1,y),z+1));

	q.push(make_pair(make_pair(x,y-1),z+1));

	q.push(make_pair(make_pair(x+1,y),z+1));

	q.push(make_pair(make_pair(x,y+1),z+1));

      }

    }

    sm+=z;

  }

  cout<<sm<<endl;

  return 0;

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

#include<deque>

#include<memory.h>



using namespace std;



int H, W, N;

char mapT[1000][1000];

int vis[1000][1000];

int temp_x = 0, temp_y;

char temp;

int final_min_route = 0;

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



struct location {

	int x, y, route;

};



location findSmallRouteBFS(int x, int y, char factory) {

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

	deque<location> que;

	location temp = { x,y,0 };

	que.push_back(temp);

	vis[x][y] = 1;

	while (!que.empty()) {

		location st = que.front();

		que.pop_front();

		if (mapT[st.x][st.y] == factory) {

			return st;

		}

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

			int t_x = st.x + dir[i][0];

			int t_y = st.y + dir[i][1];

			if (t_x < 0 || t_x >= H || t_y < 0 || t_y >= W || mapT[t_x][t_y] == 'X') {

				continue;

			}

			location temp = { t_x,t_y,st.route + 1 };

			if (!vis[t_x][t_y]) {

				vis[t_x][t_y] = 1;

				que.push_back(temp);

			}

		}

	}



}



int main() {

	cin >> H >> W >> N;

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

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

			cin >> temp;

			mapT[i][j] = temp;

			if (temp == 'S') {

				mapT[i][j] = '0';

				temp_x = i;

				temp_y = j;

			}

		}

	}



	for (int factory = 1; factory != N + 1; ++factory) {



		location lo = findSmallRouteBFS(temp_x, temp_y, mapT[temp_x][temp_y] + 1);

		temp_x = lo.x;

		temp_y = lo.y;

		final_min_route += lo.route;

	}



	cout << final_min_route << endl;

	//system("pause");

	return 0;

}

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

#include<queue>

using namespace std;



typedef struct{

 int x;

 int y;

}P;//表示坐?



char graph[1000][1000];

P aim[10];

P s,g;//s起点，g?点

int N,W,H;

int vis[1000][1000]; //用来存?距?

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



int bfs(P s,P g);



int main(){

    int i,j,t,step=0;

    cin>>H>>W>>N;

    

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

    for(j=0;j<W;j++){

        cin>>graph[i][j];

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

         t=graph[i][j]-'0';

         aim[t].x=i;

         aim[t].y=j;

      } //把1-N的坐?保存在 aim数?中 

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

          s.x=i;

          s.y=j;

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

      }//得到最初的起点 

    }

    

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

       g.x=aim[i].x;

       g.y=aim[i].y;//1-N ，从小到大，?次把一个 作??点 

       step+=bfs(s,g);

       s.x=g.x;

       s.y=g.y;//到??个?点后??点?起点 

       graph[g.x][g.y]='.';

    }

   

    cout<<step<<endl;

}



int bfs(P s,P g){

    queue<P> que;

      P n;

    

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

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

     vis[i][j]=-1;

     

     que.push(s);

     vis[s.x][s.y]=0;

     

     while(que.size()){

         

       P p=que.front();

         que.pop();

       if(p.x==g.x&&p.y==g.y)

       break;

       

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

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

           n.y=p.y+dy[i];//向四方漫射 

        if(0<=n.x&&n.x<H&&0<=n.y&&n.y<W&&graph[n.x][n.y]!='X'&&vis[n.x][n.y]==-1){

               que.push(n);

               vis[n.x][n.y]=vis[p.x][p.y]+1;

           }

       }

   }

     return vis[g.x][g.y];

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

#include<algorithm>

#include<vector>

#include<string.h>

#include<string.h>

#include<functional>

//aoj 0558

using namespace std;

int n,bs;

int hs,sl;

int dh[5]={0,0,0,1,-1};

int dll[5]={0,1,-1,0,0};

int cun[1003][1003];

struct pt{

	int hh;

	int ll;

	int step;

};

pt dl1[11];

char vis[1003][1003];

pt dl[1<<16];

void bfs(int h,int l,int gs)

{

	int qy=1<<16;

	qy--;

	memset(dl,0,sizeof(dl));

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

	int front=1;

	int back=2;

	pt ls;

	ls.hh=h;

	ls.ll=l;

	ls.step=0;

	dl[1]=ls;

	vis[h][l]=1;

	while(front<back)

	{

		pt lss=dl[front&qy];

		front++;

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

		{

			if(lss.hh+dh[i]>0&&lss.hh+dh[i]<=hs&&lss.ll+dll[i]>0&&lss.ll+dll[i]<=sl&&cun[lss.hh+dh[i]][lss.ll+dll[i]]!=111&&vis[lss.hh+dh[i]][lss.ll+dll[i]]!=1)

			{

				pt jr;

				jr.hh=lss.hh+dh[i];

				jr.ll=lss.ll+dll[i];

				jr.step=lss.step+1;

				if(cun[lss.hh+dh[i]][lss.ll+dll[i]]==gs)

				{

					bs+=jr.step;

					return;

				}else{

					dl[back&qy]=jr;

					vis[jr.hh][jr.ll]=1;

					back++;

				}

			}

		}

	}

}

int main()

{

	scanf("%d%d%d",&hs,&sl,&n);

	while(getchar()!='\n');

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

	{

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

		{

			char aaa;

			scanf("%c",&aaa);

			if(aaa=='X')

			{

				cun[i][j]=111;

			}

			if(aaa=='S')

			{

				pt ls;

				ls.hh=i;

				ls.ll=j;

				dl1[0]=ls;

				cun[i][j]=22;

			}

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

			{

				pt ls;

				ls.hh=i;

				ls.ll=j;

				dl1[aaa-'0']=ls;

				cun[i][j]=aaa-'0';

			}

		}

		

		while(getchar()!='\n');

	}

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

	{

		bfs(dl1[i].hh,dl1[i].ll,i+1);

	}

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

	return 0;

}






















// Faster C++ solution for the same problem (measured speedup: 1.6554564080129952x):
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int h,w,n;

char mp[1003][1003];

char vis[1003][1003];

int ans;

struct pt{

	int x,y;

	int st;	

};

pt st;

pt dl[1000005];

int front,back;

pt cun[21];

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

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

void bfs(int a)

{

	front=back=1;

	dl[back]=cun[a];

	back++;

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

	while(front<back)

	{

		pt ls=dl[front];

		front++;

		if(mp[ls.x][ls.y]=='0'+a+1)

		{

			ans+=ls.st;

			break;	

		}

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

		{

			int xx=ls.x+dx[i];

			int yy=ls.y+dy[i];

			if(xx>0&&yy>0&&xx<=h&&yy<=w)

			{

				if(mp[xx][yy]!='X'&&vis[xx][yy]==0)

				{

					dl[back]=(pt){xx,yy,ls.st+1};

					back++;

					vis[xx][yy]=1;	

				}

			}

		}

	}

}

int main()

{

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

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

	{

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

	}

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

	{

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

		{

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

			{

				cun[0]=(pt){i,j,0};	

			}else if(mp[i][j]<'9'&&mp[i][j]>'0')

			{

				cun[mp[i][j]-'0']=(pt){i,j,0};	

			}

		}

	}

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

	{

		bfs(i);

	}

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

	return 0;

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

#include<cstring>

#include <algorithm>

#include <queue>

#define max 1005

using namespace std;

char map[max][max];

bool vis[max][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 st,char ed)

{

    queue<node>q;

    q.push(st);

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

    while(!q.empty())

    {

        node now=q.front();

        q.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&&map[next.x][next.y]!='X'&&!vis[next.x][next.y])

            {

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

                {

                    ans+=next.time;

                    next.time=0;

                    start=next;

                    return ;

                }

                else

                {

                    q.push(next);

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

                }

            }

        }

    }

}

int main(void)

{

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

    {

        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')

                {

                start.x = i;

                start.y = j;

                start.time = 0;

                }

			}

		}

        ans=0;

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

        {

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

            BFS(start,'0'+i);

        }

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

    }

    return 0;

}

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

#include<algorithm>

#include<map>

#include<queue>

using namespace std;

#define MAX 1005



int h, w, n;

char city[MAX][MAX];

struct node{

	int x,y,time;

} start;

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

map<int,int>visited;



void dfs(char end) {

	queue<node> que;

	que.push(start);

	visited[start.x*w+start.y]=1;

	int nextx,nexty;

	while (que.size()!=0)

	{

		node now=que.front();

		que.pop();

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

			nextx=now.x + direc1[i];

			nexty=now.y+direc2[i];

			if (nextx >= 0 && nextx< h&&nexty>= 0 && nexty < w && city[nextx][nexty]!='X' && !visited[nextx*w+nexty]) {	



				if (city[nextx][nexty]==end)

				{

					start.x=nextx;

					start.y=nexty;

					start.time=now.time+1;

					return ;

				}

				else{

					visited[nextx*w+nexty]=1;

					node now1;

					now1.x=nextx;

					now1.y=nexty;

					now1.time=now.time+1;

					que.push(now1);

				}

			}

		}

	}



}







int main() {

	cin >> h >> w >> n;	

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

	{

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

		{

			cin >> city[i][j];

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

				start.x= i;

				start.y = j;

				start.time=0;

			}

		}

	}

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

		visited.clear();

		dfs(i+'1');

	}

	cout << start.time << endl;

	//system("pause");

	return 0;

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

#include <stdio.h>

#include <cstring>

#include <queue>

using namespace std;



char ma[1005][1005];int vis[1005][1005];

int w,h,n;



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

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



struct node

{

    int x,y,time;

};

node start;



void bfs(char ed)

{

    queue<node> que;

    que.push(start);

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

    while(!que.empty())

    {

        node no=que.front();

        que.pop();

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

        {

            int x=no.x+dx[i];

            int y=no.y+dy[i];

            if(vis[x][y]||x>=h||x<0||y>=w||y<0||ma[x][y]=='X')

                continue;

            if(ma[x][y]==ed)

            {

                start.x=x;

                start.y=y;

                start.time=no.time+1;

                return ;

            }

            vis[x][y]=1;

            node no1;

            no1.x=x;no1.y=y;no1.time=no.time+1;

            que.push(no1);

        }

    }

}



int main()

{

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

    {

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

        {

            scanf("%s",&ma[i]);

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

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

                {

                    start.x=i;

                    start.y=j;

                    start.time=0;

                }



        }

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

            {

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

                bfs(i+'1');

            }



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

    }

    return 0; 

}

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

#include<algorithm>

#include<map>

#include<queue>

using namespace std;

#define MAX 1005



int h, w, n;

char city[MAX][MAX];

struct node{

	int x,y,time;

} start;

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

map<int,int>visited;



void dfs(char end) {

	queue<node> que;

	que.push(start);

	visited[start.x*w+start.y]=1;

	int nextx,nexty;

	while (que.size()!=0)

	{

		node now=que.front();

		que.pop();

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

			nextx=now.x + direc1[i];

			nexty=now.y+direc2[i];

			if (nextx >= 0 && nextx< h&&nexty>= 0 && nexty < w && city[nextx][nexty]!='X' && !visited[nextx*w+nexty]) {	



				if (city[nextx][nexty]==end)

				{

					start.x=nextx;

					start.y=nexty;

					start.time=now.time+1;

					return ;

				}

				else{

					visited[nextx*w+nexty]=1;

					node now1;

					now1.x=nextx;

					now1.y=nexty;

					now1.time=now.time+1;

					que.push(now1);

				}

			}

		}

	}



}







int main() {

	cin >> h >> w >> n;	

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

	{

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

		{

			cin >> city[i][j];

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

				start.x= i;

				start.y = j;

				start.time=0;

			}

		}

	}

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

		visited.clear();

		dfs(i+'1');

	}

	cout << start.time << endl;

	//system("pause");

	return 0;

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

#define rep(i,l,n) for(int i=l;i<n;i++)

#define rer(i,l,n) for(int i=l;i<=n;i++)

#define all(a) a.begin(),a.end()

#define o(a) cout<<a<<endl

#define pb(a) push_back(a)

#define mk(a,b) make_pair(a,b)

#define fi first

#define se second

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<int,int> pii;



int change(int h,int m,int s){

	return h*3600+m*60+s;

}



int main(){

	int n;

	while(1){

		cin>>n;

		if(n==0) break;

		int sh,sm,ss,th,tm,ts,ans=0;

		vi d(86410);

		rep(i,0,n){

			scanf("%d:%d:%d %d:%d:%d",&sh,&sm,&ss,&th,&tm,&ts);

			d[change(sh,sm,ss)]++; d[change(th,tm,ts)]--;

		}

		rer(i,1,86400){

			d[i]+=d[i-1]; ans=max(ans,d[i]);

		}

		o(ans);

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.1950175469106115x):
#include <bits/stdc++.h>

#define rep(i, a, n) for(int i = a; i < n; i++)

#define repb(i, a, b) for(int i = a; i >= b; i--)

#define all(a) a.begin(), a.end()

#define o(a) cout << a << endl

// #define int long long

#define fi first

#define se second

using namespace std;

typedef pair<int, int> P;



signed main(){

    int n;

    while(1){

        cin >> n;

        if(n == 0) break;

        int h, m, s, hh, mm, ss;

        int d[24 * 3600 + 100] = {};

        rep(i, 0, n){

            scanf("%d:%d:%d %d:%d:%d", &h, &m, &s, &hh, &mm, &ss);

            int st = h * 3600 + m * 60 + s;

            int ed = hh * 3600 + mm * 60 + ss;

            d[st]++; d[ed]--;

        }

        int MAX = 0;

        rep(i, 1, 24 * 3600 + 10){

            d[i] += d[i - 1];

            MAX = max(MAX, d[i]);

        }

        cout << MAX << endl;

    }

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

#define mp make_pair

#include<cstdio>

#define MAX 86400

#include<map>

#include<algorithm>

#include<cstdlib>

#include<string>

using namespace std;

typedef pair<int,int> P;

int main(){

	int n,l,a;

	char s[20];

	P table[20000];

	while(cin>>n,n){

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

			cin>>s;

			l=atoi(s)*3600+atoi(&s[3])*60+atoi(&s[6]);

			table[i]=P(l,1);

			cin>>s;

			a=atoi(s)*3600+atoi(&s[3])*60+atoi(&s[6]);

			table[i+n]=P(a,0);

		}

		int now=0,ans=0;

		sort(table,table+2*n);

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

			if(table[i].second)

			now++;

			else now--;

			ans=max(now,ans);

		}

		cout<<ans<<endl;

	}

	return 0;

}

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

#include<cstdlib>

#include<map>

#include<algorithm>

#define mp make_pair

#include<iostream>

#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int,int> pi;

char in[20];

int n;

pi table[20000];

int main(){

	while(scanf("%d",&n),n){

		rep(i,n)rep(j,2){

			cin>>in;

			table[i*2+j]=mp(atoi(in)*3600+atoi(&in[3])*60+atoi(&in[6]),1-j);

		}

		sort(table,table+2*n);

		int ans=0,c=0;

		rep(i,2*n){

			if(table[i].second)

				c++;

			else c--;

			ans=max(ans,c);

		}

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

	}

	return 0;

}