新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
Special Judge
問題 
ある怠惰な旅行者は、必要な分より１歩も余計に歩くことなくこの街にあるできるだけ多くの面白い場所を見たいと考えています。彼は、街の最も北西の交差点に位置する彼のホテルから始めて、街の最も南東の交差点まで歩き、そしてまた歩いてホテルに戻ろうと考えています。彼は南もしくは東に向かって歩くことができるだけで、また南東の交差点から戻るときには、彼は北もしくは西に歩くことができるだけです。街の地図を見た後、いくつかの場所が通れないため、彼はこの問題がそう容易くはないことを理解しました。彼はあなたにこの問題を解決するプログラムを作成するよう頼んできました。
面白い場所と、通れない場所が示された地図(2次元のグリッド状)が与えられた時、彼が最大でいくつの面白い場所を訪れることができるかを求めてください。2回訪れた場所でも、1回としか数えられません。
入力
入力の最初の行は、テストケースの数を示す数からなります。その後にテストケースが続きます。各ケースの最初の行には、2つの整数W, H(2 <= W, H <= 100)が書かれています。W, Hはそれぞれ街の地図の横幅、縦幅を表します。続くH行には、それぞれW文字を含む文字列が書かれています。各文字の意味は次の通りです。
'.' : 歩くことができる場所
'*' : 面白い場所(歩くこともできる)
'#' : 通れない場所
あなたは、左上の交差点(始めと終わりの場所)と右下の交差点(折り返し地点)が歩くことができる場所で、この2つの交差点の間に長さH + W - 2の歩くことができる経路が存在すると仮定してかまいません。
出力
それぞれのテストケースについて、怠惰な旅行者が訪れることができる面白い場所の最大数を表す整数のみを含む1行を出力してください。
入力の例
2 9 7 *........ .....**#. ..**...#* ..####*#. .*.#*.*#. ...#**... *........ 5 5 .*.*. *###. *.*.* .###* .*.*.
出力の例
7 8
出典
Svenskt Mästerskap i Programmering/Norgesmesterskapet 2004
