https://acm.cs.nthu.edu.tw/problem/11860/

11860 - infix maze (for the EE class)   
 
Description
Determine whether a matrix contains at least a legal infix expression from the top-left corner to the bottom-right corner. If yes, convert it based on the postfix notation.
Each cell can be reached by up to four directions (up, down, right, left)
No cycles in the infix expression

The priority directions are: down>right>left>up
Matrices are consisted of 1~9, +,-,*,/, (, )
The consecutive numbers are considered as one operand
There is no negative number (e.g., -5 is illegal)
Use a space to separate operands and operators
Matrix width and height < 100
   
Some valid expression examples
12345
( ( 12345 ) )
1 + ( ( 2 ) )
Some illegal expression examples

( ) + ( 3 )
- 4 + 3
3 + ( - 4 )
+ 5 + 5
3 ( 1 + 2 )
Input
The first number is the total number of matrices.

The second and third numbers are the width and height of the first matrix.

Then the first matrix is listed.

So on and so forth.

 

Output
Repeat all inputs.

Find the first valid infix expression in the matrix.

If the matrix is found, print "Yes" then the expression, then the postfix format of the expression.

If there is no valid infix expression in the matrix, print "No"

 

Sample Input  

3
7
6
8 8 3 8 ( - 9
) / ) / / 6 2
1 ) ( - 8 ( -
) / 3 3 ( 9 6
) 7 2 2 ( / )
) 3 * * ( ) 9
6
6
9 * / 6 ( 7
3 3 8 9 4 )
7 9 ) - 3 1
( * ) 3 2 /
1 7 - ) 1 2
* 4 ( 7 7 7
8
7
9 3 5 4 - ) 9 6
2 * ) 6 + 6 + (
- 5 8 9 ( + 2 8
4 2 5 6 ( 6 ( 7
6 4 ) / ) 9 + 5
+ 9 9 9 9 + 5 (
8 + ( ( 6 1 / 5

Sample Output  

3
7
6
8 8 3 8 ( - 9
) / ) / / 6 2
1 ) ( - 8 ( -
) / 3 3 ( 9 6
) 7 2 2 ( / )
) 3 * * ( ) 9
No
6
6
9 * / 6 ( 7
3 3 8 9 4 )
7 9 ) - 3 1
( * ) 3 2 /
1 7 - ) 1 2
* 4 ( 7 7 7
Yes
9379 * ( 1 * 47 - ( 77123 ) ) - 31 / 27
9379 1 47 * 77123 - * 31 27 / -
8
7
9 3 5 4 - ) 9 6
2 * ) 6 + 6 + (
- 5 8 9 ( + 2 8
4 2 5 6 ( 6 ( 7
6 4 ) / ) 9 + 5
+ 9 9 9 9 + 5 (
8 + ( ( 6 1 / 5
Yes
92 - 46 + 8 + ( ( 61 + 99994 ) / 65258 ) * 3546 + 6 + 69 + 5 / 5
92 46 - 8 + 61 99994 + 65258 / 3546 * + 6 + 69 + 5 5 / +

Tags



Discuss



Contact us: nthucsoj@gmail.comc NTHU Online Judge 2015, Templates are from Bootswatch Project2018/4/11 14:06:49