F2 - Đua xe công thức 2
Giới hạn- Thời gian: 0.457s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đườ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 x 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 ( M, N <= 12 ). 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.
Example
Input: 4 4 **.. .... .... .... Output: 2
- Người up: beo_map
- Nguồn bài: acm.timus.ru