Đua xe công thức 2

View as PDF

Submit solution

Points: 1.78 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
acm.timus.ru
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đường đua xe công thức ~2~ năm nay nằm trong một khuôn viên hình chữ nhật chia làm ~M \times N~ ô nhỏ. Tuy nhiên trong khuôn viên này có một số ô chướng ngại vật và không thể đi vào. Tay đua cần xuất phát từ ~1~ ô bất kỳ, đi qua tất cả các ô không có chướng ngại vật, mỗi ô đúng một lần rồi quay về điểm xuất phát. Tay đua chỉ có thể đi từ ~1~ ô sang các ô kề cạnh. Hãy đếm số đường đua khác nhau có thể.

Input

Dòng đầu ghi ~2~ số ~M, N~ ~\left(M, N \leq 12\right)~.

~M~ dòng sau, mỗi dòng ghi ~N~ ký tự. Ký tự '*' thể hiện ô tương ứng có chướng ngại vật, và '.' nếu ngược lại.

Output

Gồm ~1~ số duy nhất ghi ra tổng số đường đua. Dữ liệu luôn đảm bảo kết quả nhỏ hơn ~2^{63}-1~.

Sample Input

4 4
**..
....
....
....

Sample Output

2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.