F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

circuits

Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1376    Accepted Submission(s): 487


Problem Description
  Given a map of N * M (2 <= N, M <= 12) , '.' means empty, '*' means walls. You need to build K circuits and no circuits could be nested in another. A circuit is a route connecting adjacent cells in a cell sequence, and also connect the first cell and the last cell. Each cell should be exactly in one circuit. How many ways do we have?

 

Input
  The first line of input has an integer T, number of cases.
  For each case:
  The first line has three integers N M K, as described above.
  Then the following N lines each has M characters, `.¨ or `*¨.
 

Output
  For each case output one lines.
  Each line is the answer % 1000000007 to the case.
 

Sample Input
2 4 4 1 **.. .... .... .... 4 4 1 .... .... .... ....
 

Sample Output
2 6
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-31 06:28:02, Gzip enabled