Bishops
Time limit10sMemory limit128 MB
Given an N by N board with some cells forbidden, find the maximum number of bishops that can be placed so no two attack each other along diagonals.
- Level
Medium7 of 10
- Topics
- Graph, DFS, Matrix, Backtracking
- Solved
- No attempts yet
Problem
In chess, a bishop can move any number of squares diagonally and can capture a piece on the same diagonal. In the figure below, the bishop at B can capture pieces on the cells marked O.
Some cells of the square chessboard cannot contain a bishop. In the figure below, the shaded cells are such cells. A bishop cannot be placed on those cells, but it may pass through them while moving diagonally.
If bishops are placed so that no two can capture each other, the board above can hold at most 7 bishops as shown below.
The size of the chessboard is the number of cells along one side. Given the board size and whether each cell can contain a bishop, find the maximum number of bishops that can be placed so that no two attack each other.
Input
The first line contains the board size N. N is a positive integer no greater than 10.
The next N lines describe the board, one row per line. Each row contains N integers separated by spaces. A 1 means a bishop can be placed on that cell, and a 0 means it cannot.
Output
Print the maximum number of bishops that can be placed on the given board so that no two attack each other.