1163 : 洞穴探宝

Description

Bob来到了一个带有宝藏的洞穴，他最多能够成功拿回多少宝藏呢？

洞穴的地图可以由n行m列的格子表示，其中“#”表示墙壁，“.”表示路径，“@”表示宝藏，“X”表示陷阱。 Bob可以在“.”或者“@”所在的格子自由移动，但每次只能走到上下左右相邻的某个格子中，无法进入“#”所在的格子。 特别的，Bob最多只能在“X”所在的格子停留一次，离开后会触发陷阱从而不能再次进入。 当Bob位于“@”所在的格子，或者位于“@”上下左右相邻的格子中时，即可拾取该宝藏。 Bob所能携带的宝藏的数量没有限制。

Input

包含不超过20组测试数据。

每组测试数据的第一行包含两个整数n和m，中间用一个空格隔开。 其中，3 ≤ n ≤ 100，3 ≤ m ≤ 100。

接下来包含一个n行m列的洞穴的地图。 洞穴最外围一圈只有一个“.”，其余全部是“#”，该“.”所在的位置即为洞穴的入口， Bob需要从入口进入洞穴，最终拿完宝藏之后仍需从入口离开洞穴 。 洞穴中最多包含不超过10个宝藏和不超过10个陷阱。

Output

Bob最多能够成功拿回的宝藏个数。

Sample

3 4
####
.X@#
####
3 5
#####
.X@@#
#####
7 7
##.####
##.X@@#
##X#.##
#....##
#.##.##
#X.@###
#######

1
1
2

Hint

Source

Author

Staginner