2003dc1.c

// 2003 domestic C
// 秘密の数字を整数型で保持した(これじゃダメ)
// 秘密の数字がunsigned long型の範囲内だと解ける
// 文字列で保存するようにする。
// 大小比較ができるようにしないといけない

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define ON  1
#define OFF 0

#define XX 70
#define YY 70

#define NUM(x) (x-'0')

void clear(void);
void print(int w, int h);
void search(int x, int y, char k[XX]);
void add(char s[XX], char ch);

void push(char *w);
void pop(char *w);

int sp=0;	 // スタックポインタ
char st[100][XX]; // スタック

char m[XX][YY];
int w,h;
char num[XX*YY][XX]; // 秘密の数字を保持しておく変数
size_t count, lenlen;

int main(void)
{
	int j,x,y,z;
	int flag;
	char k[XX];
	char secret[XX], num2[XX*YY][XX];
	size_t p, i, len, count2;
	int max, maxi, sum;
	
	while(1){
		scanf("%d %d", &w, &h);
		if(w==0 && h==0) break;
		
		clear();
		
		// input data
		for(j=0; j<h; j++){
			scanf("%s", m[j]);
			m[j][w]='x';
		}
//		print(w, h);
		
		count=0;
		lenlen=0;
		for(y=0; y<w; y++){
			for(x=0; x<w; x++){
				if('1'<=m[y][x] && m[y][x]<='9'){
					printf("\n%c\n", m[y][x]);
					k[0]=m[y][x];
					k[1]='\0';
					search(x, y, k);
				}
			}
		}
		
//		printf("\n");
		
		// まず秘密の数字の最長の長さを求める
		len=0;
		for(i=0; i<count; i++){
//			printf("%2d:%s\n", i, num[i]);
			if(len<strlen(num[i])){
				len=strlen(num[i]);
			}
		}
		
		// 最長の長さと同じ数字を表示
		count2=0;
		for(i=0; i<count; i++){
			if(strlen(num[i])==len){
//				printf(" %2d:%s\n", i, num[i]);
				strcpy(num2[count2++], num[i]);
			}
		}
		
		// 最大を見つける
		for(p=0; p<strlen(num2[i]); p++){
			max=0;
			maxi=0;
			for(i=0; i<count2; i++){
				if(max<NUM(num2[i][p])){
					max=NUM(num2[i][p]);
					maxi=i;
				}
			}
			sum=0;
			for(i=0; i<count2; i++){
				if(max==NUM(num2[i][p])){
					sum++;
				}
			}
			if(sum==1) break;
		}
//		printf("secret number=%s\n", num2[maxi]);
		printf("%s\n", num2[maxi]);
//		printf("\n");
	}
	return 0;
}

void push(char *w)
{
	strcpy(st[sp++], w);
}

void pop(char *w)
{
	strcpy(w, st[--sp]);
}


void add(char s[XX], char ch)
{
	char tmp[2];
	
	tmp[0]=ch;
	tmp[1]='\0';
	strcat(s, tmp);
}

void search(int x, int y, char k[XX])
{
	/*
	if(!isdigit(m[y][x])){
		printf("数字じゃなかった??：(%d,%d)=%c %s\n", x, y, m[y][x], k);
	}else
	*/
	
	if( isdigit(m[y][x+1]) && !isdigit(m[y+1][x])){ // 右だけ数字
		add(k, m[y][x+1]);
//		printf("1: (%d,%d)=%c %s\n", x, y, m[y][x], k);
		search(x+1, y, k);
	}else if(!isdigit(m[y][x+1]) &&  isdigit(m[y+1][x])){ // 下だけ数字
//		printf("2: (%d,%d)=%c %s\n", x, y, m[y][x], k);
		add(k, m[y+1][x]);
		search(x, y+1, k);
	}else if( isdigit(m[y][x+1]) &&  isdigit(m[y+1][x])){ // 右と下が数字
//		printf("3: (%d,%d)=%d %s\n", x, y, NUM(m[y][x]), k);
		push(k);
		add(k, m[y][x+1]);
		search(x+1, y, k);
		
		pop(k);
		add(k, m[y+1][x]);
		search(x, y+1, k);
	}else{ // 右と下が数字じゃない
		if(lenlen<=strlen(k)){
			lenlen=strlen(k);
//			printf("数字じゃなかった：(%d,%d)=%c %s\n", x, y, m[y][x], k);
			strcpy(num[count++], k);
		}
	}
}


void clear(void)
{
	int x,y;
	
	for(y=0; y<YY; y++){
		for(x=0; x<XX; x++){
			m[y][x]='x';
		}
	}
}

void print(int w, int h)
{
	int x,y;
	
	printf("w=%d h=%d\n", w, h);
	
	for(y=0; y<h+1; y++){
		for(x=0; x<w+1; x++){
			printf("%c ", m[y][x]);
		}
		printf("\n");
	}
	printf("\n");
}