Baby Ming and Matrix games

Accepts: 23
Submissions: 160
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
铭宝宝喜欢玩游戏,这两天他喜欢玩下面这个游戏了。
给出一个$n*m$的矩阵,矩阵的$(i*2,j*2)$ (其中$i, j = 0, 1, 2...$) 位置上为0~9的数字,矩阵中每两个数字中间有一个算术符号(+、-、*、/),其他位置用#填充。
问题是:是否能在上述矩阵中,找到一个表达式,使得表达式的计算结果为给出的sum(表达式从左到右计算)
表达式按照如下方式获取:选择一个数字作为起点,每次选择相邻的数字$X$进行一次计算,把得到的结果保存在数字$X$上,并选择该位置为下一个起点(同一个位置的数字不能使用$2$次)。
输入描述
输入$T(T \leq 1,000)$表示测试组数
输入$3$个数,奇数$n,m$以及整数$sum$(除0的式子是不合法的,除法规则见样例,$-10^{18} < sum < 10^{18}$)
接下来输入$n$行,每行$m$个字符,表示给出的矩阵(矩阵内的数字个数$\leq 15$)
输出描述
输出Possible,表示能够找到这样的表达式
输出Impossible,表示不能够找到这样的表达式
输入样例
3
3 3 24
1*1
+#*
2*8
1 1 1
1
3 3 3
1*0
/#*
2*6
输出样例
Possible
Possible
Possible
Hint
第一组样例:1+2*8=24
第三组样例:1/2*6=3