wizardrabbit   3년 전

* 본 지문은 23545번 문제를 번역하여 작성하였으며, 문제의 이해를 돕기 위해 일부 의역이나 새로운 내용이 포함되어 있을 수 있습니다.

문제


고양이 액체설에 의하면, 고양이는 액체이다. 액체인 고양이를 수조에 담아보자.

수조를 $n$ 행 $m$ 열의 격자라고 생각해 보자. 수조의 각 칸은 빈 칸이거나 장애물이 있는 칸이다.

고양이는 $k$ 의 몸집을 가지고 있다. 몸집이 $k$ 인 고양이는 수조 내에서 정확히 $k$ 칸의 공간을 차지한다.

아래의 방법대로 고양이를 수조에 넣으려고 한다.

  • 고양이가 차지할 $k$ 칸의 빈 공간을 찾아야 한다. 고양이가 차지할 빈 공간이 수조의 윗부분으로부터 장애물로 막혀 있어도 상관 없다.
  • 고양이가 아무리 액체라고 하지만, 고양이를 둘로 나눌 수는 없다. 고양이가 차지할 공간은 모두 상하좌우로 인접해 있어야 한다.
  • 위의 조건들을 만족하면서, 고양이가 있는 높이를 최대한 낮게 하려고 한다. 즉, 고양이가 차지하는 칸의 행 번호의 최솟값을 최대화하도록 하려고 한다. 행 번호는 위에서부터 $1, 2, 3, ..., n$ 과 같이 센다.

수조의 정보와 고양이의 몸집이 주어지면, 위의 방법대로 고양이를 수조에 넣었을 때 고양이가 차지하게 될 칸의 행 번호의 최솟값의 최댓값을 구하는 프로그램을 작성하시오.

입력


첫 번째 줄에 $n, m, k$ 가 공백 한 칸을 사이에 두고 차례대로 주어진다.

다음 $n$ 개의 줄에 걸쳐, $1$ 행부터 $n$ 행까지 차례대로 수조의 각 행의 정보가 공백 없이 한 줄씩 주어진다. .는 비어 있는 칸, #는 장애물이 있는 칸임을 의미한다.

출력


첫 번째 줄에, 문제에서 설명한 방법대로 고양이를 수조에 넣었을 때 고양이가 차지하게 될 칸의 행 번호의 최솟값의 최댓값을 출력한다. 만약 어떠한 방법으로도 고양이를 수조에 넣을 수 없을 경우, -1 을 출력한다.

제한


  • $1 \le n, m \le 1\;000$
  • $1 \le k \le 1\;000\;000$
  • $n, m, k$ 는 정수

2014amy   7달 전

아니... 문제 이름이 너무 귀여운거 아니에요??

댓글을 작성하려면 로그인해야 합니다.