Knight
Time limit1sMemory limit128 MB
Given an N×N board with M forbidden squares, find the maximum number of knights placeable so none attacks another.
- Level
Medium6 of 10
- Topics
- Graph, Greedy, Bit manipulation, Implementation
- Solved
- No attempts yet
Problem
The knight is a chess piece that can move from the square marked S to any of the eight squares marked X in the figure below. If another piece occupies the destination square, the knight captures it.
You are given an N×N chessboard. You want to place knights so that no two knights can capture each other in a single move. Write a program that finds the maximum number of knights that can be placed. However, knights cannot be placed on M given squares.
Input
The first line contains two integers N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ N²), separated by a space. Each of the next M lines contains the position of one square where a knight cannot be placed. Each position is given as two integers, where the top-left square of the board is (1, 1) and the bottom-right square is (N, N).
Output
Print the maximum number of knights that can be placed so that no two of them can capture each other.