Golygon およびその数を求める問題.

原問題はこちら
Golygon についての解説は こちら

Golygon とは,始点から辺の長さが1,2,3...と1つずつ増やし,90度左折または右折しながら,水平または垂直に進み,最終的に始点に戻る多角形のこと.

一般的な認識としては,辺の数 n = 8k (つまり,Golygonの辺の数が8, 16, 24, 32, ... )の時にしか Golygon が存在しないが,本問題では,始点に戻る最長辺は始点から出発する長さ1の辺と必ずしも直角でなくても良いらしく,n = 7, 8, 15, 16, ... の時に本問題でいう Golygon がつくれる.

それぞれの n での異なる Golygon リストは以下の通り.

n = 7 では 8個:
  enwnwse, eswswne, neseswn, nwswsen,
  senenws, swnwnes, wnenesw, wsesenw

n = 8 では 8個:
  enwswsen, eswnwnes, neswswne, nwsesenw,
  senwnwse, swnenesw, wneseswn, wsenenws

n = 15 では 72個:
  enenwswnwswsene, enenwswswnwnese, eneswnwnwswnese,
  eneswswswswnene, enwneswnwseswne, enwseswswsenwne,
  enwswnenwsenesw, enwswseseswnwne, enwswseswsenenw,
  esenwnwnwnwsese, esenwswswnwsene, eseswnwnwswsene,
  eseswnwswnwnese, eswnenwnwneswse, eswnwnenenwswse,
  eswnwnenwnesesw, eswnwseswnesenw, eswsenwswnenwse,
  neneswseswswnen, neneswswsesenwn, nenwseseswsenwn,
  nenwswswswsenen, nesenwseswnwsen, neswnwswswnesen,
  neswseneswnenws, neswswnwnwsesen, neswswnwswnenes,
  nwneseseseswnwn, nwneswswseswnen, nwnwseseswswnen,
  nwnwseswsesenwn, nwsenesesenwswn, nwseseneneswswn,
  nwsesenesenwnws, nwseswnwsenwnes, nwswneswseneswn,
  seneswnenwswnes, senwnesenwseswn, senwnwswnwsesen,
  senwnwswswnenes, senwswnwnwsenes, sesenwnenwnwses,
  sesenwnwnenesws, seswnenenwnesws, seswnwnwnwneses,
  swneneseneswswn, swnenesesenwnws, swnenwswneswsen,
  swneseneneswnws, swnwsenwnesenws, swsenenenenwsws,
  swsenwnwnenwses, swswnenenwnwses, swswnenwnenesws,
  wnenwseneswsenw, wnesenwneswnwse, wneseswseswnwne,
  wneseswswsenenw, wneswseseswnenw, wnwneseneseswnw,
  wnwnesesenenwsw, wnwsenenesenwsw, wnwsesesesenwnw,
  wsenenwnenwswse, wsenenwnwnesesw, wseneswsenwswne,
  wsenwnenenwsesw, wseswnesenwnesw, wswneneneneswsw,
  wswneseseneswnw, wswseneneseswnw, wswsenesenenwsw

n = 16 では 112個 (数が多いので,詳細は次のC言語ソースプログラムを参照).

上の表現法では,東,北,南,西への進行方向をそれぞれ e, n, s, w で表現している.

例えば,n = 7 での最初の Golygon は enwnwse と書いてあるので,始点(原点)から,東へ1歩,北へ2歩,西へ3歩,北へ4歩,西へ5歩,南へ6歩,東へ7歩,と歩けば,最初の始点(原点)に戻れることを意味する.

なお,本問題の出力フォーマットに従い、上記のリストは e, n, s, w の辞書式順序に沿ってソートしてある.

通り道に障害物のない Golygon を表示し,その数を累計すれば,本問題はこれで解ける.

C言語解答プログラム: Solution for UVa 225 Golygons (C program)
計算時間: 0.047秒

Comments are closed.

Post Navigation