그림자
시간 제한2초메모리 제한128 MB
격자 방에 점광원 하나와 빛을 막는 벽이 있을 때, 빈 공간 중 빛이 도달하지 못하는 그림자 영역의 넓이를 구하는 문제입니다.
문제
크기가 N x M인 직사각형 방이 1 x 1 단위 칸으로 나뉘어 있다. .은 빈 칸, #은 빛을 가로막는 벽, *은 광원을 나타낸다. 광원은 정확히 하나이며, * 칸의 중심에 있는 점으로 본다.
방 안의 빈 칸에 있는 한 점과 광원을 잇는 선분이 어떤 벽 칸의 내부와도 만나지 않으면, 그 점에는 빛이 도달한다. 그렇지 않은 빈 공간은 그림자가 된다. 벽 칸은 빛을 막지만, 구해야 하는 넓이에는 포함하지 않는다.
방의 정보가 주어졌을 때, 그림자인 빈 공간의 넓이를 구하라.
입력
첫째 줄에 자연수 N과 M이 주어진다. N과 M은 50보다 작거나 같다.
둘째 줄부터 N개의 줄에 방의 모양이 주어진다. .은 빈 칸, #은 벽, *은 광원이다. 광원은 정확히 하나만 주어진다.
출력
첫째 줄에 그림자의 넓이를 출력한다. 절대 오차 또는 상대 오차가 10^-9 이하이면 정답으로 인정된다.