■

今年の情報オリンピック予選のこの問題、

冬の寒いある日，JOI太郎君は広場にはった薄氷を割って遊ぶことにした．広場は長方形で，東西方向に m 個，南北方向に n 個，つまり， m × n の区画に区切られている．また，薄氷が有る区画と無い区画がある． JOI太郎君は，次のルールにしたがって，薄氷を割りながら区画を移動することにした．

薄氷があるどの区画からも薄氷を割り始めることができる．

東西南北のいずれかの方向に隣接し， まだ割られていない薄氷のある区画に移動できる．

移動した先の区画の薄氷をかならず割る．

JOI太郎君が薄氷を割りながら移動できる区画数の最大値を求めるプログラムを作成せよ．ただし， 1 ≦ m ≦ 90，1 ≦ n ≦ 90 である．与えられる入力データでは，移動方法は20万通りを超えない．

入力

入力はn+2行ある． 1 行目には整数 m が書かれている． 2 行目には整数 n が書かれている． 3 行目から n+2 行目までの各行には、0 もしくは 1 が， 空白で区切られて m 個書かれており，各区画に薄氷があるか否かを表している．北から i 番目，西からj番目の区画を (i,j) と記述することにすると (1 ≦ i ≦ n, 1 ≦ j ≦ m)，第 i+2 行目の j 番目の値は，区画 (i,j) に薄氷が存在する場合は 1 となり，区画 (i,j) に薄氷が存在しない場合は 0 となる．

のいい最適化の方法が思いつかない。

一応プログラムは書けたけど90*90の時にまともに動く気がしない。

単なる深さ優先検索。

array = [
  [1, 1, 1, 0, 1],
  [1, 1, 0, 0, 0],
  [1, 0, 0, 0, 1]
]
result = []
def get(x, y):
  if (0 <= x < len(array)) and (0 <= y < len(array[0])):
    return array[x][y]
  else:
    return -1
def func(x, y, route):
  route = route[:]
  # print x, y, get(x, y)
  if get(x, y) == 0:
    result.append(route)
    return
  if (x, y) in route:
    return
  route.append((x, y))
  if get(x - 1, y ) >= 0: func(x - 1, y , route)
  if get(x , y + 1) >= 0: func(x , y + 1, route)
  if get(x + 1, y ) >= 0: func(x + 1, y , route)
  if get(x , y - 1) >= 0: func(x , y - 1, route)
func(0, 0, [])
for i in result:
  print i

Permalink | 記事への反応(3) | 19:08

ツイートシェア