TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2037
  • Problem
  • P2037【CQOI2012】局部极小值
    Limits : Time Limit : 20000 MS   Memory Limit : 165536 KB
    Description

    有一个n行m列的整数矩阵,其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。
      给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。

    Input Format

    输入第一行包含两个整数n和m(1<=n<=4, 1<=m<=7),即行数和列数。以下n行每行m个字符,其中“X”表示局部极小值,“.”表示非局部极小值。

    Output Format

    输出仅一行,为可能的矩阵总数除以12345678的余数。

    Sample Input

    样例输入1:
    1 3
    .X.
    样例输入2:
    2 2
    X.
    .X
    样例输入3:
    3 2
    X.
    ..
    .X
    样例输入4:
    3 6
    ....X.
    ......
    .X...X

    Sample Output

    样例输出1:
    2
    样例输出2:
    0
    样例输出3:
    60
    样例输出4:
    869490

    Hint

    【样例解释】
    在第一个样例中,只有两个可能的矩阵:213、321。