KOI 본선 2007 중5- 비숍2(bishop) > 문제은행 : 정보올림피아드&알고리즘



1118 : 비숍2(bishop)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
15 회   
시도횟수
40 회   

문제

서양장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같이 크기가 5인 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

 



그런데 체스판 위에는 비숍이 지나갈 수 없는 장애물이 놓일 수 있다. 예를 들어 < 그림 2 >와 같이 체스판 중앙에 비숍이 지나갈 수 없는 장애물이 놓이면 비숍은 장애물 오른쪽 아래 대각선 방향으로는 움직일 수 없다.
 

 



정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판에 놓인 장애물들의 위치가 주어질 때, 체스판 위에 서로가 서로를 잡을 수 없도록 하면서 최대 몇 개의 비숍을 놓을 수 있는지를 구하는 프로그램을 작성하시오.


예를 들어 < 그림 2 >와 같이 체스판이 주어지면 < 그림 3 >과 같이 서로가 서로를 잡지 못하도록 하면서 최대 10개의 비숍을 놓을 수 있다.

 

입력형식

첫째 줄에 정사각형 체스판의 크기 N이 주어진다.

둘째 줄에는 체스판 위에 놓인 장애물의 개수 M이 주어진다. 

 

N은 100이하의 자연수이고 M은 음이 아닌 정수이다. 이어 셋째 줄부터 한 줄에 하나씩 장애물의 위치가 주어진다. 

장애물이 놓인 칸의 위치는 위에서부터 몇 번째 행인지와 왼쪽부터 몇 번째 열인지를 나타내는 두 개의 자연수가 차례로 주어진다.


출력형식

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

입력 예

5
1
3 3

출력 예

10


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP