지리지도
시간 제한1초메모리 제한128 MB
격자에서 마을 표시 'x'와 가로로 쓰인 대문자 이름 문자열이 주어질 때 인접 관계와 유일성 조건을 이용해 각 마을의 이름을 찾아 위치와 이름을 출력합니다.
문제
지리지도는 R행 C열의 문자 격자로 주어진다.
어떤 작은 나라의 지도에서 마을은 소문자 x로 표시된다. 각 마을의 이름은 알파벳 대문자로 이루어진 한 행의 연속한 문자열이며, 왼쪽에서 오른쪽으로 읽는다.
마을 이름은 해당 마을의 위치 옆에 적혀 있다. 즉, 그 이름을 이루는 문자 중 적어도 하나가 마을 칸과 8방향으로 인접한 칸 중 하나에 있다.
한 마을 근처에 여러 이름이 있을 수 있고, 한 이름 근처에 여러 마을이 있을 수도 있다. 하지만 주어진 지도에서는 각 마을의 위치와 이름을 항상 결정할 수 있다.
각 마을의 위치와 이름을 찾아 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 행 수 R과 열 수 C가 주어진다. (1 ≤ R ≤ 50, 1 ≤ C ≤ 50)
다음 R개의 줄에는 지도를 나타내는 길이 C의 문자열이 주어진다. 각 문자는 ., x, 또는 알파벳 대문자이다.
마을 이름은 모두 서로 다르다. 같은 행에 여러 마을 이름이 있으면, 서로 적어도 하나의 . 또는 x로 구분된다.
출력
각 마을의 행 번호, 열 번호, 이름을 한 줄에 하나씩 출력한다. 행은 위에서부터 1부터 R까지, 열은 왼쪽부터 1부터 C까지 번호를 매긴다.
마을의 이름을 결정하는 방법이 여러 가지이면 그중 아무 방법으로 출력해도 된다. 출력 순서는 자유롭다.