← 返回题目列表

Codeforces · 2073/A

A. 控制塔

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Control Towers - 原题 PDF 第 1 页
原题PDF第1页
Control Towers - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Problem A
                      Control Towers
                     Time limit: 2 seconds


You are an architect tasked with designing the new airport in your city. After you have completed your design, you
just realize you forgot to allocate spaces for the control towers.

The layout of the new airport can be represented by a 2D grid of r rows and c columns, with the rows numbered from
1 to r (top to bottom) and the columns numbered from 1 to c (left to right). The cell in row i and column j is denoted
by (i, j). Each cell can either be occupied or empty.

You need to place four control towers (numbered from 1 to 4), each in a different empty cell. To allow easier commu-
nication between different towers, for all k = 1, 2, 3, you want tower k and tower k + 1 to be placed either in the same
row or in the same column.

You want to calculate the number of ways to place the control towers to satisfy the requirements above. Two ways are
considered different if there exists k where control tower k is placed in different cells.

Input

The first line of input contains two integers r and c (1 ≤r, c ≤2000). Each of the next r lines contains a string of c
characters. The j-th character in the i-th line is # if cell (i, j) is occupied; otherwise, it is . (dot).

Output

Output the number of ways to place the control towers to satisfy the requirements above.


 Sample Input #1                          Sample Output #1

 3 4                                    10
 .#.#
 #...
 .###


Explanation for the sample input/output #1

Figure A.1 illustrates all 10 possible ways to place the control towers, where the cells numbered 1, 2, 3, and 4 represent
control towers 1, 2, 3, and 4 respectively.

       1  #  2  #       1  #  2  #      .  #  1  #      .  #  1  #       4  #  3  #
      #  4  3  .      #  .  3  4      #  3  2  4      #  4  2  3      #  1  2  .
      .  #  #  #      .  #  #  #      .  #  #  #      .  #  #  #      .  #  #  #

      .  #  4  #       3  #  2  #      .  #  4  #       4  #  3  #       2  #  3  #
      #  1  3  2      #  .  1  .      #  2  3  1      #  .  2  1      #  .  4  .
      .  #  #  #       4  #  #  #      .  #  #  #      .  #  #  #       1  #  #  #

                          Figure A.1: All 10 possible ways to place the control towers.




The 2025 ICPC Asia Pacific Championship Problem A: Control Towers

Sample Input #2                          Sample Output #2

 4 6                                    0
 ######
 #.#.#.
 .#.#.#
 ######


Explanation for the sample input/output #2

It is impossible for any control tower in row 2 to be in the same column as any control tower in row 3. Since there are
not enough empty cells to place all four control towers in the same row, there is no way to place the control towers to
satisfy the requirements above.


 Sample Input #3                          Sample Output #3

 1 10                                   5040
 ..........


Explanation for the sample input/output #3

All 10 × 9 × 8 × 7 = 5040 ways of control tower positions satisfy the requirements above.


 Sample Input #4                          Sample Output #4

 1 10                                   0
 ##########


Explanation for the sample input/output #4

There is no empty cell to place any control tower.





The 2025 ICPC Asia Pacific Championship Problem A: Control Towers