题目描述
给定一个整数 D,n 行 m 列的实数矩阵 A,其第 i 行第 j 列的元素是 aij,且 0≤aij≤D(1≤i≤n,1≤j≤m)。希望你能由此提供一个 n 行 m 列的 01 矩阵 B,第 i 行 第 j 列的元素是 bij(1≤i≤n,1≤j≤m),bij 非 0 即 1。
对于给定的 A 矩阵和你提供的 B 矩阵,可以求出
p1=max⎩⎨⎧1≤j≤mmax{∣∑i=1n(bij−Daij)∣}1≤i≤nmax{∣∑j=1m(bij−Daij)∣}p2=1≤i≤n,1≤j≤mmax{∣bi,j+bi−1,j+bi,j−1+bi−1,j−1−Dai,j+ai−1,j+ai,j−1+ai−1,j−1∣}在不同的测试例子中,我们希望提供的 B 矩阵能使 p1 或 p2 尽量小。
输入格式
第一行有一个整数 c,有两种取值:c=1 表示我们的最小化目标是 p1,c=2 则表示希望 p2 尽量小。
第二行有3个整数 D,n,m,相邻的两个数字间用一个空格隔开,D 的含义如上文所述,n 和 m 分别表示 A 矩阵的行数和列数。
以下有 n 行,每行 m 个实数,描述 A 矩阵。其中第 i 行第 j 列的实数表示 aij,相邻的数字用一个空格隔开。
输出格式
仅包含一个 n 行 m 列的 01 矩阵 B,表示你求出的使 pc 尽量小的答案。其中第 i 行第 j 列的数字表示 bij。相邻的整数之间用一个空格隔开。
提示
对于 40% 的数据,c=1;
对于 60% 的数据,c=2;
对于 100% 的数据,2≤n,m≤700,1≤D≤109。