302671: CF518F. Pasha and Pipe
Memory Limit：512 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Pasha and Pipe
题意翻译
现在要在一个城市中铺设管道。 这个城市是由 n×m 小方格组成的。每一个小方格要么是空的（管道可以铺设在上面），要么是实的（管道不能铺在上面）。空的用’.’表示，实的用’#’表示。 管道铺设的规则如下： · 整条管道是形状是宽度为1的折线； · 管道只能铺设在空的格子上面； · 管道的两个端点只能在边缘上，但是不能在角上； · 管道最多只能转两个弯（90度）； · 在管道上的格子有且只能有两个是在边缘上的； · 如果管道是一条直线，那么他的两个端点必须是落在不同的边上； · 对于管道上的非边缘格子，每一个格子会有且仅有两个相邻的其它格子在管道上； · 对于管道上处于边缘的格子，仅有一个相邻的格子处于管道上。 下面有一些合法的管道铺设例子： ``` ....# ....# .*..# ***** ****. .***. ..#.. ..#*. ..#*. #...# #..*# #..*# ..... ...*. ...*. ``` 下面是一些非法铺设的例子： ``` .**.# *...# .*.*# ..... ****. .*.*. ..#.. ..#*. .*#*. #...# #..*# #*.*# ..... ...*. .***. ``` 这些例子中管道用’*’表示。 现在给定城市的地图，请计算一下有多少种方法铺设管道。 样例解释： 在第一个样例中，有三种方法铺设管道（管道用'*'表示）。 ``` .*. .*. ... .*# **# **# .*. ... .*. ```题目描述
On a certain meeting of a ruling party "A" minister Pavel suggested to improve the sewer system and to create a new pipe in the city. The city is an $ n×m $ rectangular squared field. Each square of the field is either empty (then the pipe can go in it), or occupied (the pipe cannot go in such square). Empty squares are denoted by character ' $ . $ ', occupied squares are denoted by character ' $ # $ '. The pipe must meet the following criteria: - the pipe is a polyline of width $ 1 $ , - the pipe goes in empty squares, - the pipe starts from the edge of the field, but not from a corner square, - the pipe ends at the edge of the field but not in a corner square, - the pipe has at most $ 2 $ turns ( $ 90 $ degrees), - the border squares of the field must share exactly two squares with the pipe, - if the pipe looks like a single segment, then the end points of the pipe must lie on distinct edges of the field, - for each non-border square of the pipe there are exacly two side-adjacent squares that also belong to the pipe, - for each border square of the pipe there is exactly one side-adjacent cell that also belongs to the pipe. Here are some samples of allowed piping routes: `<br></br> ....# ....# .*..#<br></br> ***** ****. .***.<br></br> ..#.. ..#*. ..#*.<br></br> #...# #..*# #..*#<br></br> ..... ...*. ...*.<br></br>`Here are some samples of forbidden piping routes: `<br></br> .**.# *...# .*.*#<br></br> ..... ****. .*.*.<br></br> ..#.. ..#*. .*#*.<br></br> #...# #..*# #*.*#<br></br> ..... ...*. .***.<br></br>`In these samples the pipes are represented by characters ' $ * $ '. You were asked to write a program that calculates the number of distinct ways to make exactly one pipe in the city. The two ways to make a pipe are considered distinct if they are distinct in at least one square.输入输出格式
输入格式
The first line of the input contains two integers $ n,m $ ( $ 2<=n,m<=2000 $ ) — the height and width of Berland map. Each of the next $ n $ lines contains $ m $ characters — the map of the city. If the square of the map is marked by character ' $ . $ ', then the square is empty and the pipe can through it. If the square of the map is marked by character ' $ # $ ', then the square is full and the pipe can't through it.
输出格式
In the first line of the output print a single integer — the number of distinct ways to create a pipe.
输入输出样例
输入样例 #1
3 3
...
..#
...
输出样例 #1
3输入样例 #2
4 2
..
..
..
..
输出样例 #2
2
输入样例 #3
4 5
#...#
#...#
###.#
###.#
输出样例 #3
4