2003年度予選課題:最長連鎖探索問題SuperCon実施委員会)

二次元格子状に9種類の記号が隙間なく配置されている. (図1の場合にはA〜Eの5種類.)


	図1
                 
          CCCDDDCDDD
          BCBADBCBAD
          DBBAAAAAEE
          CDBBBAAEAE
          BCAABBAAAE
          BCBADBCBAD
          CDBBCCCBAD
          CBADDBCCDB
          CCCDDDCDDD
          BCBADBCBAD

ある記号からみて,左,もしくは右,あるいは下に隣接する同種の 記号の列(これを「連鎖」と呼ぶ)を考える(図2).


	図2

          左←A→右   このどれかに記号Aが隣接していれば
              ↓       連鎖としてつなぐことができる.
              下       

たとえば,記号Aの連鎖に関しては,図1の場合,図3(a) の赤い 連鎖(長さ6)や,あるいは図3(b) の青い連鎖(長さ11)が 見つかる.


        図3
          CCCDDDCDDD         CCCDDDCDDD
          BCBDBCBAD         BCBDBCBAD
          DBBAAAAAEE         DBBAAAAAEE
          CDBBBABEAE         CDBBBBEAE
          BCAABAAAAE         BCAABAAAAE
          BCBABBCBAD         BCBABBCBD
          CDBBCCCBAD         CDBBCCCBD
          CBADDBCCDB         CBADDBCCDB
          CCCDDDCDDD         CCCDDDCDDD
          BCBADBCBAD         BCBADBCBAD

                  (a)                           (b)
          ・・・・・・・・・・         ・・・・・・・・・・
          ・・・・・・・・・         ・・・・・・・・・
          ・・・AAAAA・・         ・・・AAA・・・・
          ・・・・・・・・・・         ・・・・・・・・・
          BCAABAAAAE         ・・・・・AAAA・
          BCBABBCBAD         ・・・・・・・・・
          CDBBCCCBAD         ・・・・・・・・・
          CBADDBCCDB         ・・・・・・・・・・
          CCCDDDCDDD         CCCDDDCDDD
          BCBADBCBAD         BCBADBCBAD
連鎖を見つける時は,どの位置からスタートしてもよい.図4の例では,その中から6つの連鎖を 示す.

        図4
         AAAAAA
         ・・・・A・
         ・・・AA・

        1)   →AAAAAA
        2)     AAAAAA←
        3)   →AAAA
                     A
                   AA
        4)         AA←
                   A
                 AA
        5)     →AA   左下.上には行けないのでここでストップ
        6)       AA←
この例では,3のケースが一番長い連鎖となっている.

【問題】 AからIまで9種類の記号が二次元格子状に配列された大きさN の正方平面が与えられたとき,最長連鎖の記号,開始位置,その長さ を求めなさい.同じ長さの連鎖が複数ある場合にも,そのうちの1つを 求めればよい.

注意:
1.位置について.左上隅の格子点を(0,0)とし下方を正のY座標, 右方を正のX座標とする.格子点間を単位1と数える.

入力形式
N=100を仮定.横100個,縦に100行分のAからIまでの1バイト文字が 埋まっているテキストファイルを仮定する.文字と文字の間には空白等は存在しない.

出力形式
記号の種類 X座標 Y座標 長さ


(参考:入出力プログラム例,エラー処理は除く)
#include <stdio.h>
#include <string.h>
#define N 100
#define MAX 2048

char Table[N][N];
int main(int argc, char *argv[])
{
	int i, j;
	FILE *fp;
	char buf[MAX];
	char longest; /* 最長連鎖を形成する記号の種類 */
        int x, y;  /* 座標 */
	int longest_path; /* 最長連鎖の長さ */

	fp = fopen(argv[1],"r");
	for(i=0; i<N; i++){
		char *p;
		p=fgets(buf, MAX, fp);
		for (j=0; j < N; j++)
			Table[i][j] = buf[j];
	 }
	fclose(fp);

	/* 以下結果を計算するプログラム */
	/*		:               */

	printf("%c %d %d %d\n", longest, x, y, longest_path);
	exit(0);
}