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 BCBADBCBAD BCBADBCBAD DBBAAAAAEE DBBAAAAAEE CDBBBABEAE CDBBBABEAE BCAABAAAAE BCAABAAAAE BCBABBCBAD BCBABBCBAD CDBBCCCBAD CDBBCCCBAD CBADDBCCDB CBADDBCCDB CCCDDDCDDD CCCDDDCDDD BCBADBCBAD BCBADBCBAD (a) (b) ・・・・・・・・・・ ・・・・・・・・・・ ・・・A・・・・・・ ・・・A・・・・・・ ・・・AAAAA・・ ・・・AAA・・・・ ・・・・・・・・・・ ・・・・・A・・・・ BCAABAAAAE ・・・・・AAAA・ BCBABBCBAD ・・・・・・・・A・ CDBBCCCBAD ・・・・・・・・A・ 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つを 求めればよい. 注意:
|