問題設定は A 問題と同一のものですが、制約のみが異なりますのでご注意ください。
北海道大学に合格し、新たな生活の始まりに心を躍らせるほむらちゃん。しかし彼女の前には、とてつもなく広いキャンパスが待ち受けていた...。
「え...次の授業に間に合わないんだけど...」
北海道大学札幌キャンパスは異常に広いことで有名です。札幌キャンパスは縦に H マス、横に W マス並んだ長方形のマス目で表現されます。北から i マス、西から j マス進んだマスを (i,j) で表すことにします。キャンパス内にはいくつか建物があり、マス (i,j) で表される位置に建物がある場合は 'B' 、ない場合は '.' が c_{i,j} に書かれています。
北海道大学の新入生のほむらちゃんは、キャンパスのあまりの広さに驚愕し、建物間の移動が心配になってきました。そこで、建物のある 2 つのマスのうち、最も遠い組はどれくらい離れているのかが気になりました。ここで、2 つのマスの組 (i,j) , (i',j') の間の距離を |i-i'|+|j-j'| と定義します。
ほむらちゃんは、自分にはこの問題は難しいと思い、同級生のあなたに助けを求めてきました。ほむらちゃんの代わりに答えを求めてください。
H W c_{11}c_{12} ... c_{1W} : c_{H1}c_{H2} ... c_{HW}
答えを表す整数を 1 行に出力せよ。
3 3 B.B ..B .BB
4
4 3 B.. B.. ... ...
1
6 6 ...B.. B.B.B. .B.B.B ...B.B .B..B. ..B...
7