룩 배치하기
시간 제한1초메모리 제한128 MB
폰이 놓인 N×N 보드에서 서로 잡히지 않게 놓을 수 있는 룩의 최대 개수를 구합니다.
문제
체스에서 룩은 자기가 있는 행이나 열을 따라 원하는 칸까지 이동한다. 두 룩이 같은 행이나 같은 열에 있고 그 사이를 막는 것이 없으면 서로 잡을 수 있다.
아무것도 놓이지 않은 N × N 체스판에 서로 잡지 못하게 룩을 최대한 많이 놓는 문제는 쉽다. 대각선을 따라 한 칸씩, 모두 N개를 놓으면 된다.
여기에 폰을 더해 보자. 폰이 서 있는 칸은 룩이 지나가지 못한다. 그래서 사이에 폰이 있으면 같은 행이나 같은 열에도 룩을 여러 개 놓을 수 있다. 폰이 놓인 체스판이 주어질 때, 어느 두 룩도 서로 잡지 못하게 놓을 수 있는 룩의 최대 개수를 구하라.
룩은 빈 칸에만 놓는다.
입력
첫 줄에 체스판의 크기 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개의 줄에는 길이가 N인 문자열이 한 줄씩 주어진다. '.'은 빈 칸이고, 'X'는 폰이 있는 칸이다.
출력
놓을 수 있는 룩의 최대 개수를 한 줄에 출력한다.