N M
c_{11}c_{12}…c_{1M}
c_{21}c_{22}…c_{2M}
:
:
c_{N1}c_{N2}…c_{NM}

• 1 行目は、街の南北の長さとして整数 N(1≦N≦500) と東西の長さとして整数 M(1≦M≦500) が空白で区切られて与えられる。
• 2 行目から N 行は、格子状の街の各区画における状態 c_{ij} がそれぞれ s, g, 1-9, # のいずれかで与えられる。
• i+1 行目 j 文字目の文字 c_{ij} は、座標 (j,i) が下記のような状態であることを表す。
  • s : その区画が学校であることを表す。
  • g : その区画が自宅であることを表す。
  • 1-9 : その区画の日当たりの良さを表す。
  • # : その区画に侵入出来ないことを表す。
• 与えられた街の外を通ることは出来ない。
• s と g はそれぞれ 1 つずつ与えられ、s と g は隣接していない。