17075번 - 유물 복원 스페셜 저지

서울 Y모 대학에서 끊임없이 소음과 분진을 발생시키며 공사를 진행하던 중, 고대 유물로 추정되는 석판 하나가 발굴되었다. 이 석판은 N개의 행과 M개의 열로 나누어진 격자 형태로, 각 칸은 텅 빈 칸이거나 사람 한 명이 그려진 칸이었다. 석판은 아쉽게도 온전한 형태로 발굴되지는 않았으며, 칸들 중에는 일부가 부서져 있어 내용을 식별할 수 없는 칸도 있었다.

그 후 얼마 지나지 않아, 관련 자료를 통해 이 석판의 규칙을 알 수 있게 되었다. 이 석판에서 가능한 모든 부분 직사각형에 대해 내부의 사람 수를 구하고, 그 수들을 모두 더해서 얻는 값이 K의 배수여야 한다는 것이다. 0은 모든 수의 배수가 될 수 있다.

예를 들어, 2 × 2 크기의 아래 석판을 보자.

위 석판에는 아래와 같이 9개의 부분 직사각형이 있다.

각 부분 직사각형 내부의 합은 1, 0, 0, 1, 1, 1, 1, 1, 2가 되고, 이들의 총합은 8이 된다.

학교 측은 얻은 정보를 토대로 석판을 가능한 형태 중 하나로 복원하기 위해 연세대학교 컴퓨터과학과에 복원작업을 의뢰하었고, 자연스럽게 이 과제는 2019 교내 대회의 문제로 출제되게 되었다. 당신은 석판의 형태와 K를 입력으로 받아 석판의 복원이 가능한지 알아보고, 가능할 경우 조건을 만족하는 석판 하나를 복원해야 한다.

첫째 줄에 석판의 행의 수 N과 열의 수 M, 문제에 제시된 K가 주어진다. (1 ≤ N, M ≤ 50, 2 ≤ K ≤ 2500)

둘째 줄부터 N+1번째 줄까지, 각 줄에 M개의 정수 a_i,j가 공백으로 구분되어 주어진다. (a_i,j ∈ { -1, 0, 1})

a_i,j  = -1일 경우 석판의 i번째 행 j번째 열이 부서져 있음을, a_i,j  = 0 일 경우 해당 칸이 비어 있음을, a_i,j  = 1일 경우 해당 칸에 사람 한 명이 그려져 있음을 의미한다.

복원이 가능할 경우 첫 줄에 1을, 불가능할 경우 -1을 출력한다.

만약 첫 줄에 1을 출력했다면, 이어 N개의 줄에 M개의 정수로 행렬에 존재하는 모든 -1을 0 또는 1로 대체하여 문제의 조건에 맞게 복원한 석판 하나를 출력한다. 입력에서 -1이 아니었던 모든 칸은 입력과 동일해야 하며, -1인 모든 칸은 0 또는 1 중 하나로 복원되어야 한다.

조건을 만족하는 석판이 여러 가지라면 아무 것이나 하나만 출력한다.

부분 직사각형이란, 행을 위부터 1, 2, …, N으로 번호를 매기고 열을 왼쪽부터 1, 2, …, M으로 번호를 매길 때, 1 ≤ r₁ ≤ r₂ ≤ N, 1 ≤ c₁ ≤ c₂ ≤ M인 어떤 r₁, r₂, c₁, c₂에 대하여 행의 번호가 r₁ 이상 r₂ 이하이며, 열의 번호가 c₁ 이상 c₂ 이하인 모든 칸의 집합을 뜻한다. 가능한 모든 부분 직사각형이란, 부등식을 만족하는 모든 서로 다른 (r₁,c₁,r₂,c₂)에 대해 한 번씩 직사각형을 만든 것을 뜻한다.