Khu đô thị SuperVilla có qui hoạch giống như một hình chữ nhật gồm ~m \times n~ ô đất, ô đất thứ ~i~ từ phía Bắc và ~j~ từ phía Tây gọi là ô ~(i,j)~. Trên mỗi ô đất, nhà đầu tư sẽ quyết định xây một ngôi biệt thự hoặc một công trình công cộng mang tầm cỡ quốc gia.
Vì là khu đô thị cao cấp nên các con đường sẽ nối từ ô đất này sang ô đất khác, đồng thời các con đường sẽ chỉ có một chiều. Cụ thể, từ một ô đất ~(x,y)~ có một con đường dẫn tới ô đất ~(x+1,y)~ và ~(x,y+1)~ nếu hai ô này tồn tại; mặt khác các công trình công cộng là bị cấm đi vào (nhằm tránh thiệt hại không đáng có cho công trình quốc gia)
Quân và Hiển là đôi bạn thân, nhưng do vì bị o rờ dét nhiều quá nên Hiển
cảm thấy Quân rất phiền và lăn ra dỗi; không vừa, Quân dùng chiến thuật
"gậy ông đập lưng ông" cũng quay ra dỗi ngược; thế là mình mất nhau
hai người dỗi nhau. Trước đó Quân và Hiển đã hẹn cùng nhau mua nhà tại khu
SuperVilla, tiền đã cọc nên không thể bùng kèo. Và họ quyết định mua hai
ngôi biệt thự sao cho từ nơi ở của Quân không thể đến được nơi ở của
Hiển và từ nơi ở của Hiển cũng không thể đến được nơi ở của Quân
Yêu cầu: Quân và Hiển không thèm nói chuyện với nhau nên không thống nhất được phương án. Bạn hãy giúp Quân và Hiển đếm số cách mua biệt như vậy nhé. Hai cách mua gọi là khác nhau nếu vị trí của hai căn biệt thự là khác nhau trong hai cách (Xem test ví dụ).
Input
Dữ liệu vào từ file văn bản villa.inp
Dòng đầu chứa hai số nguyên dương ~m,n~ (~1 \le m,n \le 2000~).
~m~ dòng tiếp, dòng thứ ~i~ chứa ~n~ kí tự ~a_{i,1},a_{i,2},…,a_{i,n}~ thuộc một trong hai loại {.,#} mô tả khu SuperVilla; nếu ~a_{i,j}=~ '.' thì trên ô ~(i,j)~ xây một ngôi biệt thự, ngược lại thì trên đó là một công trình công cộng cấp quốc gia.
Dữ liệu đảm bảo tất cả các biệt thự đều có đường đi tới từ ô đất ~(1,1)~ và có đường đi tới ô đất ~(m,n)~ mà không đi qua các công trình công cộng mang tầm cỡ quốc gia.
Output
Kết quả in ra file văn bản villa.out
- In ra một số nguyên duy nhất là số cách mua nhà của Quân và Hiển mà bạn tìm được.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~25~ | ~m,n \le 50~ |
2 | ~35~ | ~m,n \le 400~ |
3 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
3 3
..#
..#
#..
Sample Output 1
1
Giải thích
Chỉ có một cách mua là chọn hai căn biệt thự ~(1, 2)~ và ~(2, 1)~.
Comments