폭발을 일으켜 거대한 기름 유출을 유발할 석유 시추 시설을 건설하기 전에, 실제로 석유를 찾아야 합니다. 물론, 석유가 없더라도 이론적으로는 건설 및 폭발 부분은 작동하겠지만, 기름 유출을 발생시키려면 정말로 석유가 필요합니다.
비용과 이익에 주로 관심을 두는 회사들은 가능한 한 저렴하게 추출할 수 있는 석유를 찾기를 원합니다. 관련 요인이 더 많지만, 가격의 주요 구성 요소는 석유를 찾기 위해 얼마나 깊이 시추해야 하는지와 어떤 물질을 뚫어야 하는지입니다.
이 문제에서는 특정 유전의 크기는 무시합니다. 당신은 해저 지도를 받고, 각 지점에서 시추하는 데 드는 비용을 계산하도록 요청받을 것입니다.
입력
첫 번째 줄은 입력 데이터 세트의 수 K이며, 그 뒤에 K개의 데이터 세트가 다음 형식으로 이어집니다.
각 데이터 세트의 첫 번째 줄에는 1 <= h, w <= 40인 두 개의 정수가 포함됩니다. 이들은 각각 해저 지도의 높이(h)와 너비(w)입니다.
이어서 h개의 줄이 나오며, 각 줄은 w개의 대문자로 이루어진 문자열입니다. 문자열의 각 문자는 다음 중 하나입니다.
'X' (해당 위치에 석유가 있음)
'H' (단단한 경암(Hard Rock)을 나타냄)
'S' (부드러운 연암(Soft Rock)을 나타냄)
경암(H)을 뚫는 데는 단위 암반당 3의 비용이 들고, 연암(S)을 뚫는 데는 단위 암반당 1의 비용이 듭니다.
w개의 각 위치에 대해, 최상단에서부터 첫 번째 석유(X)가 발견될 때까지 수직으로 시추하는 데 드는 비용을 계산해야 합니다. 일부 위치에서는 석유를 전혀 발견하지 못할 수도 있으며, 이 경우 비용 대신 문자 'N'을 출력해야 합니다.
출력
각 데이터 세트에 대해, 한 줄에 "Data Set x:"를 출력합니다. 여기서 x는 해당 데이터 세트의 번호입니다.
다음 줄에는 w개의 위치 각각에 대해 석유까지 시추하는 데 드는 w개의 비용을 왼쪽에서 오른쪽 순서로 출력하고, 각 비용은 단일 공백으로 구분됩니다 (줄 끝에는 공백이 없어야 합니다). w번째 위치에서 석유를 사용할 수 없는 경우, 해당 위치에 대해서는 비용 대신 'N'을 출력해야 합니다.
blackbee4 1년 전 1
폭발을 일으켜 거대한 기름 유출을 유발할 석유 시추 시설을 건설하기 전에, 실제로 석유를 찾아야 합니다. 물론, 석유가 없더라도 이론적으로는 건설 및 폭발 부분은 작동하겠지만, 기름 유출을 발생시키려면 정말로 석유가 필요합니다.
비용과 이익에 주로 관심을 두는 회사들은 가능한 한 저렴하게 추출할 수 있는 석유를 찾기를 원합니다. 관련 요인이 더 많지만, 가격의 주요 구성 요소는 석유를 찾기 위해 얼마나 깊이 시추해야 하는지와 어떤 물질을 뚫어야 하는지입니다.
이 문제에서는 특정 유전의 크기는 무시합니다. 당신은 해저 지도를 받고, 각 지점에서 시추하는 데 드는 비용을 계산하도록 요청받을 것입니다.
입력
첫 번째 줄은 입력 데이터 세트의 수 K이며, 그 뒤에 K개의 데이터 세트가 다음 형식으로 이어집니다.
각 데이터 세트의 첫 번째 줄에는 1 <= h, w <= 40인 두 개의 정수가 포함됩니다. 이들은 각각 해저 지도의 높이(h)와 너비(w)입니다.
이어서 h개의 줄이 나오며, 각 줄은 w개의 대문자로 이루어진 문자열입니다. 문자열의 각 문자는 다음 중 하나입니다.
경암(H)을 뚫는 데는 단위 암반당 3의 비용이 들고, 연암(S)을 뚫는 데는 단위 암반당 1의 비용이 듭니다.
w개의 각 위치에 대해, 최상단에서부터 첫 번째 석유(X)가 발견될 때까지 수직으로 시추하는 데 드는 비용을 계산해야 합니다. 일부 위치에서는 석유를 전혀 발견하지 못할 수도 있으며, 이 경우 비용 대신 문자 'N'을 출력해야 합니다.
출력
각 데이터 세트에 대해, 한 줄에 "Data Set x:"를 출력합니다. 여기서 x는 해당 데이터 세트의 번호입니다.
다음 줄에는 w개의 위치 각각에 대해 석유까지 시추하는 데 드는 w개의 비용을 왼쪽에서 오른쪽 순서로 출력하고, 각 비용은 단일 공백으로 구분됩니다 (줄 끝에는 공백이 없어야 합니다). w번째 위치에서 석유를 사용할 수 없는 경우, 해당 위치에 대해서는 비용 대신 'N'을 출력해야 합니다.
각 데이터 세트 뒤에는 빈 줄 하나가 이어져야 합니다.