【AtCoder】Beginner Contest 377-B.Avoid Rook Attack

Problem Statement

题目链接
There is a grid of $64$ squares with $8$ rows and $8$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top $(1\le i\le 8)$ and $j$-th column from the left $(1\le j\le 8)$.

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence $(S_1,S_2,S_3,\dots ,S_8)$ of $8$ strings of length $8$. Square $(i,j)$ $(1\le i\le 8,1\le j\le 8)$ is empty if the $j$-th character of $S_i$ is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square $(i,j)$ can capture pieces that satisfy either of the following conditions:

• Placed on a square in row $i$
• Placed on a square in column $j$

For example, a piece placed on square $(4,4)$ can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• Each $S_i$ is a string of length $8$ consisting of . and # $(1\le i\le 8)$.

Input

The input is given from Standard Input in the following format:

$S_1$
$S_2$
$S_3$
$S_4$
$S_5$
$S_6$
$S_7$
$S_8$

Output

Print the number of empty squares where you can place your piece without it being captured by any existing pieces.

Sample Input 1

...#....
#.......
.......#
....#...
.#......
........
........
..#.....

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on $4$ squares: square $(6,6)$, square $(6,7)$, square $(7,6)$, and square $(7,7)$.

Sample Input 2

........
........
........
........
........
........
........
........

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

.#......
..#..#..
....#...
........
..#....#
........
...#....
....#...

Sample Output 3

4

解法

题目中说，假如当前位置有元素，那么当前位置的一行和一列上都不能放其他元素。让我们计算出还有多少个位置可以放元素。

那么，我们使用一个二维 bool 类型的数组存储是否可以放元素。

如果位置 map[i][j] 上有元素，那么就将 st[0][j] 和 st[i][0] 都标记为 true 表示有元素。

统计答案时，只需要有统计没有元素的位置就可以了，即 st[j][0] 和 !st[0][i] 都为 false 即可。

具体代码如下：

char map[10][10];
bool st[9][9];
void solved() {/* your code */for (int i = 1; i <=8; i ++) {for (int j = 1; j <= 8; j ++) {cin >> map[i][j];if (map[i][j] == '#') {// 在列上标记st[0][j] = 1;// 在行上标记st[i][0] = 1;}}}int sum = 0;for (int i = 1; i <= 8; i ++) {for (int j = 1; j <= 8; j ++) {// 寻找行和列都为 false 的情况if(!st[j][0] && !st[0][i]) sum ++;}}cout << sum << endl;
}

总结

这道题目因为数据规模很小，所以我们可以使用二维数组存标记去题，但是如果数据量规模较大，使用二维数组存起来的方法必然失效。对于数据量规模较大的题目，下次将会分享具体做法。