Chat noir

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem L: シャノワール

なつめは学校からの帰り道、見慣れない野良ねこを見つけた。とてもかわいい黒ねこだったので一緒に遊びたかったのだが、なつめを見るなり逃げだしてしまった。どうしても仲良くなりたいなつめは、道をふさいでねこを捕まえることにした。捕まえようとすると、ねこの機嫌を多少損ねてしまうだろうが、あとで仲直りすればいいのだ。

ねこが逃げこんだ空き地は、まわりが囲まれていない草地で、便宜上 H x W マスの正方グリッドで表現することにする.それぞれのマスは何も無いか障害物が置いてあるかのどちらかである。

最初、あるマスにねこが居座っている。以後、なつめとねこは以下のターンを交代で繰り返す。

  1. なつめが任意のマスに障害物をひとつ置く。空き地内の何もないマスであればどこでも置くことができるが、既に障害物が置いてあるマスや、ねこが現在いるマスには障害物を置くことはできない。
  2. ねこが移動する。ねこは今居るマスの上下左右どれかに隣り合うマスに移動することができる。ただし、障害物のあるマスに入ることはできない。また、ねこがグリッドの端のマスにいる場合、空き地から外に出ることができる。

ねこが空き地の外に出ると逃げていってしまい、ねこが動けなくなったらなつめはねこを捕らえることができる。

初期の障害物配置とねこの位置が与えられる。なつめとねこがお互いに最適の戦略を取った時、ねこが逃げ出せるかどうか判定するプログラムを作成してほしい。

Input

入力の1行目には、グリッドのサイズを表わす整数H, Wが1つの空白文字を挟んで含まれている。 続くH行は、ちょうど長さがWの文字列である。これはちょうどH x Wのグリッドを表わしており、各マスとそこに書かれた文字は以下のように対応する。

.なにもないマス
#障害物のあるマス
@ねこの初期位置

ねこはちょうど1匹のみであることが保証されている。初期状態で空マスが1つ以上存在する。3 ≤ H, W ≤ 100を満たす。

Output

ねこが逃げられるなら "The neko can escape!", 逃げられないなら "The neko will be caught." という文字列を1行で出力せよ。末尾にエクスクラメーションマークあるいはピリオドが必要であることに注意すること。

Notes on Submission

上記形式で複数のデータセットが与えられます。入力データの 1 行目にデータセットの数が与えられます。各データセットに対する出力を上記形式で順番に出力するプログラムを作成して下さい。

Sample Input

4
5 6
.....#
..#...
..@#..
.....#
##....
5 6
.....#
..#..#
..@#..
.....#
##....
4 4
#...
#...
#@..
####
7 7
.......
.......
.......
...@...
.......
.......
.......

Output for the Sample Input

The neko can escape!
The neko will be caught.
The neko will be caught.
The neko can escape!

Source: University of Tokyo Programming Contest 2009 , Tokyo, Japan, 2009
Problem Setter:  Shuhei Takahashi
http://www.utpc.jp/2009/