第８回日本情報オリンピック　予選４

2008年12月23日
情報オリンピック日本委員会

問題
４ 		　　　薄氷渡り

解説

ここでは，本問題を再帰を用いて解く方法を解説する．

まず最初に，薄氷が張られている広場をデータとして読み込まなければならない． これは，サイズが (m+2)×(n+2) となる２次元配列を用いると便利であろう．

たとえば，入力例１の場合だと，図1のようにデータを格納する． 図1中，枠で囲まれた部分が配列に格納されているデータであり， また，黄色で示されている部分が入力ファイルから読み込んだデータである． 周りを囲むように0が入力されているが，これはプログラム内で配列の端であるか否かを判断する手間を省くためである．

0 1 2 3 4
0 0 0 0 0 0
1 0 1 1 0 0
2 0 1 0 1 0
3 0 1 1 0 0
4 0 0 0 0 0
図1：データを読み込んだ直後の配列

次に，再帰を用いて移動できる区画の最大値を求める方法の基本的なアイディアを説明する． たとえば，図1において(1,1)から薄氷を割り始めることを考えてみよう（図2の青い部分）．

0 1 2 3 4
0 0 0 0 0 0
1 0 1 1 0 0
2 0 1 0 1 0
3 0 1 1 0 0
4 0 0 0 0 0
図2：(1,1)から割り始める場合

次に割る場所としては，(2,1)と(1,2)が考えられる． 今回は，(1,2)を割ることにしよう． その結果，図3のようになる．

0 1 2 3 4
0 0 0 0 0 0
1 0 0 1 0 0
2 0 1 0 1 0
3 0 1 1 0 0
4 0 0 0 0 0
図3：(1,1)を割り，(1,2)に移動した直後の様子

図3において，(1,1)の薄氷（赤い部分）は，割ってしまったので値が0となっている． また，今後，図3において(1,2)から薄氷を割り始める場合を考えれば良い．割れる枚数は，

すでに割った枚数（この例だと1枚）＋ 図3において(2,1)から薄氷を割り始めて移動可能な最大区画数

になる．

この説明の中で， 図kにおいて(x,y)から薄氷を割り始める という表現が繰り返し出てきている． つまり，この部分は同一の処理を行っている．したがって,

入力：現在の薄氷のある区画を表す図k, 次に割り始める座標(x,y), すでに割った枚数depth

となる関数を作成し，関数内で繰り返し呼び出せばよい（再帰呼び出しをすればよい）．

東西南北に薄氷のある区画がなかったとき，再帰呼び出しは終了する． そのときの depth+1 が，そのルートをたどった場合の区画数となる． グローバル変数に今までの最大値max_depthを保存しておき，max_depthよりdepth+1の方が大きければ， max_depthの値をdepth+1に更新する．

このような関数を作成し，すべての区画から始めることを考え， 最後にmax_depthを出力すればよい．

次に，実際にプログラムを書くことを考えよう．入力が『現在の薄氷のある区画を表す図k, 次に割り始める座標(x,y), すでに割った枚数』である関数は，以下のような構造にすればよいだろう．ここで，グローバル変数max_depthには，今まで試してみた中で，一番多くの区画を通ったときの区画数を保存しておくことにする． 

int check2(int table[N][M],int x, int y, int depth){

  table[x][y]=0; // 現在いる場所の薄氷を割る
  if(table[x-1][y]==1){  // 隣接する西側の区画に薄氷がある場合
    check2(table,x-1,y,depth+1);  // そちらにすすんだ場合を考える
  }
  if(table[x+1][y]==1){  //隣接する東側の区画に薄氷がある場合
    check2(table,x+1,y,depth+1);//  // そちらにすすんだ場合を考える
  }
  if(table[x][y+1]==1){ // 隣接する南側の区画に薄氷がある場合
    check2(table,x,y+1,depth+1); // // そちらにすすんだ場合を考える
  }
  if(table[x][y-1]==1){ // 隣接する北側の区画に薄氷がある場合
    check2(table,x,y-1,depth+1); // // そちらにすすんだ場合を考える
  }
  table[x][y]=1; // 割った氷を元に戻しておく

  if((table[x][y+1]||table[x][y-1]||table[x+1][y]||table[x-1][y])==0){
  	 // 東西南北，どちらにも薄氷がない場合
    if(depth+1 > max_depth){ 
    	 // このパスを通って割った枚数が，
    	 // 今までたどった中で一番多くの区画を通っているならば，
      max_depth=depth+1;  // 最長の区画数を更新する
    }
    return(0);
  }
}

最後に例として，この関数を，check(table,1,1,0) として呼び出した場合の推移を示す．