C言語関係掲示板

過去ログ

No.904 連結最大数字列(ICPC 2003年度 国内予選問題)

[戻る] [ホームページ]
No.669

連結最大数字列(ICPC 2003年度 国内予選問題)
投稿者---ため息(2003/11/15 17:44:53)


今、この問題をやっているんですが、うまくできずこまっています。
どなたかお分りになれば、指導いただけると幸いです。
お願いします。

sizex×sizey の長方形の領域があり、 1×1の各マスには英字または
数字が書かれている。 数字だけを右または下に辿ってできる数字列を考え、
それらの数字列を数の表現とみた時にできる数の中で最大の数を出力しなさい。
例えば、7×4の長方形領域が

  ---------------------------
 | 9 | R | 2 | A | 9 | 9 | 3 |
 |---+---+---+---+---+---+---|
 | 0 | E | 3 | 1 | 4 | A | 0 |
 |---+---+---+---+---+---+---|
 | 8 | A | 9 | 0 | 0 | D | E |
 |---+---+---+---+---+---+---|
 | 8 | 2 | 0 | R | 0 | 3 | 7 |
  ---------------------------

であれば、

 7 4
 9R2A993
 0E314A0
 8A900DE
 820R037

という入力となる。 先頭の行は 横、縦のサイズで、 2行目以降に 7×4
の領域の状態を与えている。 この入力であれば、

 23900037

と出力するプログラム。

注意/参考として、

sizex、sizeyは正整数で、sizex + sizey≦70 である。
英字は大文字だけ現われる。
極めて大きな数となる可能性があることに注意。
先頭にある 0 を出力してはいけない。
例えば、

 20 2
 01234567891234CBDEGH
 BDEDF908034265091499

という入力であれば、出力は次のようになる
(この数値は longでも表現できないであろう大きな値であることにも注意)。

 12345908034265091499

考え方としては、
領域情報を 2次元配列で表わす。
右あるいは下に調べていくので、領域外か否かを容易に調べられるよう、
2次元配列の右側と下側に数字以外の値を入れて番兵とするとよい。
現在調べている数字列、および それまでに見つけた最大の数字列を蓄えて
おくために、2つのデータを用意する。
これらは 1次元配列とそこに含まれる数字の長さとからなる。
なすべき動作を抽出して、それぞれを関数とする。
例えば、
標準入力からデータを入力して 2次元配列に設定する
得られた最大数字列を出力する
2つの数字列の大小を比較する
バックトラックで調べる本体
調べる最初の位置を求めてバックトラックを呼び出す
全体の制御を行なう main
という役割とそれに対応する関数
をつくりたいと思います。

数字列の途中を始点とする探索は明らかに無駄であるので、これを
避ける工夫もしたいと思います。

尚、以下の例題を利用したいと思います。

sizex×sizey の長方形の領域があり、 各マスには石が置かれているか
いないかのどちらかである。 これらの石は縦・横でつながっていれば同じグループ
に属するとみなされる。

例えば、6×5 の領域が
.X.X.X
.X.XX.
XX..X.
.X.X.X
..XXX.

となっていれば (X は石あり、. は石なしを表わす)、5個のグループがあるが、
これらのグループを認識し、各グループに1から始まる識別番号を付けよ、
という問題である。 上記の領域であれば、
. 1 . 2 . 3
. 1 . 2 2 .
1 1 . . 2 .
. 1 . 4 . 5
. . 4 4 4 .
のように出力するプログラム。

/* 縦横で連結したグループを見つける */
#include <stdio.h>

#define MaxSize 100    /*横・縦の最大*/
#define NotYet   -1    /*未だグループ化されていない石を表わす印*/
#define Outside  -9    /*領域外を表わす番兵*/

int sizex,sizey;       /*横・縦の大きさ*/
int area[MaxSize+2][MaxSize+2];  /*各マスの状態(Outside/NotYet/grp番号)*/

void inarea()
/* 'X'/'.'のsizex*sizeyのデータをarea[][]に読み込む */
{ int c;
  int x,y;
  scanf("%d %d", &sizex,&sizey);
  for(y=0; y<=sizey+1; y++)
    for(x=0; x<=sizex+1; x++) area[x][y] = Outside;
  for(y=1; y<=sizey; y++)
    for(x=1; x<=sizex; x++) {
      while((c = getchar()) != '.' && c != 'X') ;
      area[x][y] = (c=='X') ? NotYet : 0;
    }
}

void outarea()
/* area[][]の出力 */
{ int x,y;
  for(y=1; y<=sizey; y++) {
    for(x=1; x<=sizex; x++)
      if     (area[x][y] == 0)      printf("  .");
      else if(area[x][y] == NotYet) printf("  X");
      else                          printf("%3d", area[x][y]);
    printf("\n");
  }
}

void group(int x, int y, int grp)
/* (x,y)を含むグループに番号grpを付ける */
{
  if(area[x][y] == NotYet) {
    area[x][y] = grp;
    group(x+1,y,grp); group(x-1,y,grp);
    group(x,y+1,grp); group(x,y-1,grp);
  }
}

void grouping()
/* 連結した部分にグループ番号(1-)を付ける */
{ int grp = 0;
  int x,y;
  for(y=1; y<=sizey; y++)
    for(x=1; x<=sizex; x++)
      if(area[x][y] == NotYet) group(x,y,++grp);
}

int main()
{
  inarea();
  grouping();
  outarea();
}


No.671

Re:連結最大数字列(ICPC 2003年度 国内予選問題)
投稿者---あかま(2003/11/16 04:09:16)


面白そうだったのでとりあえず問題を解くだけのプログラムを作ってみました。
strcpyばっかり使って効率は良くないと思います。
>数字列の途中を始点とする探索は明らかに無駄であるので、これを
>避ける工夫もしたいと思います。
これはプログラム中で考えてません。
どうやったら実現できるでしょうかね?なかなか難しい。
っと、いま思いつきました。
探索開始点の左と上を見てそれが数字だったら数字列の途中ですね。


#include <stdio.h>
#include <string.h>
#define size 70

char matrix[size][size];
char max[size*2];
int maxlen;

comp(char *se,int selen){//検索中の文字列とそれまでで最大の文字列を比較
	if(maxlen > selen) return;
	if(maxlen == selen && strcmp(max,se) >= 0) return;
	strcpy(max,se);
	maxlen = selen;
}

search(int y,int x,char *se,int selen){
	char se2[size*2];
	
	comp(se,selen);
	//printf("%d %s\n",selen,se);
	if(matrix[y][x+1] >= '0' && matrix[y][x+1] <= '9'){
		strcpy(se2,se);
		se2[selen] = matrix[y][x+1];se2[selen+1] = '\0';
		search(y,x+1,se2,selen+1);
		
	}
	if(matrix[y+1][x] >= '0' && matrix[y+1][x] <= '9'){
		strcpy(se2,se);
		se2[selen] = matrix[y+1][x];se2[selen+1] = '\0';
		search(y+1,x,se2,selen+1);
	}
	
}
main(){
	int sizex,sizey,y,x;
	char se[size*2]={0};
	//読み込み
	scanf("%d %d",&sizex,&sizey);
	for(y = 0;y < sizey;y++){
		scanf("%s",matrix[y]);
	}
	
	//ここから検索
	for(y = 0;y < sizey;y++){
		for(x = 0;x < sizex;x++){
			if(matrix[y][x] > '0' && matrix[y][x] <= '9'){
				se[0]= matrix[y][x];
				search(y,x,se,1);
			}
		}
	}
	printf("answer\n%s\n",max);
}


No.672

Re:連結最大数字列(ICPC 2003年度 国内予選問題)
投稿者---ため息(2003/11/16 08:52:07)


お返事ありがとうございます。
とても参考になります。
あかまさんのプログラムを参考にして、関数を作って
自分のやり方で実現したいと思います。
また分からないことあったら聞くと思いますが、その機会には指導の方
お願いします。

No.673

Re:連結最大数字列(ICPC 2003年度 国内予選問題)
投稿者---かずま(2003/11/16 12:23:02)


> 面白そうだったのでとりあえず問題を解くだけのプログラムを作ってみました。
> strcpyばっかり使って効率は良くないと思います。

再起呼び出しの関数が配列を持っているとスタックの消費が気になりますね。
私も作ってみました。
#include <stdio.h>
#include <string.h>

#define in_0_9(c)  ((unsigned)(c) - '0' < 10)
#define in_1_9(c)  ((unsigned)(c) - '1' < 9)

#define N  70

char b[N+1][N+1], c[N+1], d[N+1];
int maxlen = 0;

void search(int y, int x, int len)
{
    c[len] = b[y][x];
    if (in_0_9(b[y][x+1])) search(y, x+1, len+1);
    if (in_0_9(b[y+1][x])) search(y+1, x, len+1);
    if (!in_0_9(b[y][x+1]) && !in_0_9(b[y+1][x])) {
        c[len+1] = 0;
        if (len > maxlen || len == maxlen && strcmp(c, d) > 0)
            maxlen = len,  strcpy(d, c);
    }
}

int main(void)
{
    int sizex, sizey, y, x;

    if (scanf("%d%d", &sizex, &sizey) != 2) return 1;
    if (sizex <= 0 || sizey <= 0 || sizex + sizey > N) return 1;
    for (y = 1; y <= sizey; y++)
        for (x = 1; x <= sizex; x++)
            if (scanf(" %c", &b[y][x]) != 1) return 1;
    for (y = 1; y <= sizey; y++)
        for (x = 1; x <= sizex; x++)
            if (in_1_9(b[y][x]) && !in_1_9(b[y-1][x]) && !in_1_9(b[y][x-1]))
                search(y, x, 0); 
    puts(d);
    return 0;
}


No.674

Re:連結最大数字列(ICPC 2003年度 国内予選問題)
投稿者---mtk(2003/11/16 17:38:03)


>私も作ってみました。

暫定最長のものとの比較は、あかまさんのように
毎回チェックする方が少し速いようです。
(平均の処理が軽くなるということでしょうか)

void search(int y, int x, int len)
{
    c[len] = b[y][x], c[len+1] = 0;
    if (len > maxlen || len == maxlen && strcmp(c, d) > 0)
        maxlen = len,  strcpy(d, c);

    if (in_0_9(b[y][x+1])) search(y, x+1, len+1);
    if (in_0_9(b[y+1][x])) search(y+1, x, len+1);
}

>char b[N+1][N+1], c[N+1], d[N+1];

あと、これは無駄ですね。

char b[N+1][N+1], c[N], d[N];

 N = 70 の時、最大の数字列は 69(N-1) 以下なので。



No.678

Re:連結最大数字列(ICPC 2003年度 国内予選問題)
投稿者---ため息(2003/11/16 23:26:01)


かずまさん、mtkさん御返事ありがとうございました。
返事遅くなり申し訳ございません。
各プログラムを参考に作れそうです。
ほんとにありがとうございました。