PawnsOnChessBoard | Topcoder Archive

Problem Statement

You are given a String[] chessBoard representing a chess board, where the c-th character of the r-th element represents the square at row r, column c. An empty square is represented by '.' and an occupied square is represented by '#'. All coordinates in this problem are given as (row, column). Your task is to place pawns on the board using the following algorithm:

for each row r from first to the last
  for each column c from first to the last
    if square at position (r, c) is empty and 
    not attacked by pawn
      place pawn on square at position (r, c)

A pawn at square (r, c), where r is not the last row, attacks square (r + 1, c + 1) (if c is not the last column) and also square (r + 1, c - 1) (if c is not the first column).

Return the number of pawns that are placed on the board using this algorithm.

Definition

Class:: PawnsOnChessBoard
Method:: placingPawns
Parameters:: String[]
Returns:: int
Method signature:: int placingPawns(String[] chessBoard)
(be sure your method is public)

Constraints

chessBoard will contain between 1 and 50 elements, inclusive.
Each element of chessBoard will contain between 1 and 50 characters, inclusive.
All elements of chessBoard will be of the same length.
Each character of each element of chessBoard will be either '.' or '#'.

Examples

```
{"#..#.",
 "...##",
 "#.##."}
```
```
Returns: 5
```
Using the described algorithm, 5 pawns are placed on the board. The diagram below shows the state of the board after each new pawn is placed ('P' - pawn; 'X' - attacked square): 01234 01234 01234 01234 01234 0 #P.#. #PP#. #PP#P #PP#P #PP#P 1 X.X## --> XXX## --> XXX## --> XXX## --> XXX## 2 #.##. #.##. #.##. #P##. #P##P
```
{"..##.",
 "..###",
 "....."}
```
```
Returns: 8
```
```
{"######",
 "######",
 "######",
 "######"}
```
```
Returns: 0
```
If all squares are occupied we can't place any pawns on the board.
```
{"#####",
 "#####",
 "##.##",
 "#####",
 "#####"}
```
```
Returns: 1
```
There is only one empty square, and we can place a pawn there.

{"........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........"}

Returns: 32

On a standard empty chess board, you can place 32 pawns so that no pawn is attacked by any other pawn.

{"###.#.######.#.##.####.#.##.##.##.######",
 "##################.#######.###.#####.##.",
 "###########.#.#.#############.###.#...##",
 "#.####..##.#####..#.###.####.######.#.##",
 ".########..##.########.#.#######.##.#.##",
 "#.####.#####.#####.###.######.#####.####",
 "#.####..#..##.###.###.#.##.#.######..###",
 "###.######..#.#######.##.##.#########.##",
 "###.#.####.#.###.###.######.############",
 "###.###.##..##.####.#.##.###########.##.",
 "#####.###.###.#..######.###..#.##.#####.",
 "#..###..####.##########.######.#######.#",
 "###.....#.########.##.####.#############",
 "..#.###.####.##.##.#####..########...##.",
 "#.###.####.##.#########..##.######.#####",
 "#.###..##.######.##..######.#..###.#####",
 "####.##.##...####..###.##########.######"}

Returns: 112

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.