벽이나 격자 끝에 부딪힐 때까지 굴러가는 공으로 격자 위의 모든 별을 모을 수 있는지 판정한다.
보통7그래프BFS시뮬레이션비트 연산아직 제출이 없습니다시간 제한1초메모리 제한256 MB
문제 설명
예제2
문제
재민이는 퍼즐 게임 앱을 만들었다.
격자 위에 공이 하나 놓여 있다. 공은 상하좌우 중 한 방향으로 굴릴 수 있고, 한 번 굴러가기 시작하면 벽에 부딪히거나 격자의 끝에 닿을 때까지 그 방향으로 계속 굴러간다. 어떤 칸에는 별이 놓여 있어서, 공이 그 칸에 멈추거나 그 칸을 지나가면 사용자가 그 별을 얻는다. 목표는 격자에 있는 별을 모두 얻는 것이다.
이 앱에는 레벨 에디터가 있어서 사용자가 직접 레벨을 만들어 공유할 수 있다. 어느 날 재민이는 "만든 레벨을 풀 수 있는지 검사하는 기능을 넣어 주세요!"라는 건의를 받았다. 글쎄, 말이야 쉽지만...
격자가 주어지면 모든 별을 얻을 수 있는지 판정하는 프로그램을 작성하시오.
입력
첫째 줄에 격자의 높이 H와 너비 W가 주어진다. (1≤H,W≤50)
둘째 줄부터 H개의 줄에 격자의 각 행을 나타내는 길이 W의 문자열이 차례대로 주어진다. #은 벽, .은 빈 칸, O는 공, *는 별이다. 격자에 공은 정확히 한 개 있고, 별은 적어도 한 개 있다.
cho.sh