Description

Input

第一行包含三个正整数 \(n, m, p\), 表示矩阵的行数列数以及每个数的范围, 接下来 \(n\) 行每行包含 \(m\) 个非负整数, 其中第 \(i\) 行第 \(j\) 个数表示以格子 \((i, j)\) 为右下角的 \(2 \times 2\) 子矩阵中的数的和. 保证第一行与第一列的数均为 \(0\), 且每个和都不超过 \(4(p-1)\).

Output

包含 \(n\) 行, 每行 \(m\) 个整数, 描述你求出的矩阵, 相邻的整数用空格分开. (行末不要有多余空格)

Sample Input

3 3 3
0 0 0
0 4 5
0 5 3

Sample Output

0 0 2
2 2 1
1 0 0

Data Range

对于所有数据, 满足:\(1 \leq n, m \leq 200, 1 \lt p \leq 10\)

Explanation

不停地出矩阵瞎搞而且连标题都没有变是要怎样......

而且行尾不要输出多余空格!! !

然而这道题并不会做, 看上去以为是一道瞎搞搜索, 结果一看题解果然是神搜索. 然而那种 奇怪的推断函数并没有弄明白, 所以就直接贴题解 (然而最后的复杂度分析我也是醉了):

原文链接:http://www.cnblogs.com/yangjiyuan/p/5321082.html

首先可以知道, 如果已知第一行和第一列的数, 那么可以很容易的计算出其余的数. 进一步的, 如果笔算将每个数的表达式写出可以得出如下结论:

第 \(i\) 行的第 \(j\) 个数 (\(i \gt 1, j \gt 1\)) 只与 \((1, 1), (i, 1), (1, j)\) 有关

更数学化地说, 设输入矩阵为 \(S\), 定义 \(C\) 如下:

\[C_{i,j} = \begin{cases} 0 & i = 1\ \text{or}\ j = 1\\ S_{i,j} - C_{i,j-1} - C_{i-1,j} - C_{i-1,j-1} & \text{else} \end{cases}\]

则原矩阵 \(A\) 的第 \(i\) 行的第 \(j\) 个数可按下式确定:

\[A_{i,j} = f(i) \cdot A_{i,1} + f(j) \cdot A_{1,j} - f(i) \cdot f(j) \cdot A_{1,1} + C_{i,j} (i \gt 1\ \text{and}\ j \gt 1)\]

\[f(x) = \begin{cases} 1 & (x \bmod 2 = 1)\\ -1 & (x \bmod 2 = -1) \end{cases}\]

算法一:

直接利用该结论, 枚举第一行和第一列的每个数, 从而求出剩下所有数, 并判断是否符合要求. 时间复杂度 \(O(n \cdot m \cdot p^{n+m-1})\), 较好的实现可以通过 30% 的数据.

算法二:

考虑 \(p=2\) 的情况, 每个格子只有两种取值 0/1. 首先枚举 \((1,1)\), 那么第一行某个格子 \((1,j)\) 与第一列某个格子 \((i,1)\) 唯一确定了格子 \((i,j)\), 若 \((1,j)=x\) 且 \((i,1)=y\) 时 \((i,j)\) 的取值不合法, 则 \((1,j)\) 取 \(x\) 和 \((i,1)\) 取 \(y\) 不能同时发生.

这是经典的 2-SAT 模型, 虽然使用拓扑排序可以在 \(O(n \cdot m)\) 的时间内求出一个可行解, 但无法求出字典序最小解. 这里应使用枚举算法, 按字典序的优先级判断每一个点, 若该点的取值未确定, 先尝试放 \(0\), 看是否产生矛盾, 无矛盾则确定为 \(0\) 否则改为 \(1\). 该算法的时间复杂度为 \(O((n+m) \cdot n \cdot m)\), 较好的实现可以通过 30% 的数据.

算法三:

结合算法一与算法二可以通过 60% 的数据.

算法四:

对于一般的情况, 2-SAT 模型并不适用, 但可以尝试将算法二稍做修改. 即每次从 \(0\) 到 \(p-1\) 枚举取值, 找到最小的且不与前面产生矛盾的确定为该格的值. 遗憾的是, 该算法是 错误的, 很多时候这样做甚至会丢失可行解! 为了避免这种情况, 可以使用 DFS 算法.

具体来说, 依次枚举第一行每个格子的取值, 每次枚举后判断第一列每个格子是否均有可行的取值, 若没有则退出, 否则继续枚举下一个格子. 若第一行的格子均已确定, 则第一列的每个格子直接取可行取值中最小的即可.

由于数据保证有解, 对于矩阵较大的情况, 解很多, 限制很多, 搜索树的宽度很小, 而矩阵较小时搜索树深度很小, 均可以较快的得出答案. 更进一步的, 在矩阵较大时, 基本上不会有回溯的情况, 即时间复杂度约等于 \(O(n \cdot m \cdot p^2)\), 可以通过所有测试数据.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 210;

int even(int in) {
    return (in & 1) ? -1 : 1; }
int odd(int in) {
    return (in & 1) ? 1 : -1; }

int n, m, p;
int arr[maxn][maxn], // Initial array, read-only
    comp[maxn][maxn], // Values need to be added to this location
    vmn[maxn][maxn], // Minimum allowed value at location
    vmx[maxn][maxn], // Maximum allowed value at location
    res[maxn][maxn]; // Final result

bool dfs(int j)
{
    // Construction complete.
    if (j > m)
        return true;
    // Leftmost value in this row.
    for (int k = 0; k < p; k++) {
        bool satisfy = true;
        res[1][j] = k;
        // Checking for satisfaction at this row.
        for (int i = 2; i <= n; i++) {
            int tmp_1 = (comp[i][j] + res[1][1] * even(i+j+1) + res[1][j] *
                    odd(i)) * even(j),
                tmp_2 = (comp[i][j] + res[1][1] * even(i+j+1) + res[1][j] *
                    odd(i) - p + 1) * even(j);
            if (tmp_1 > tmp_2)
                swap(tmp_1, tmp_2);
            vmn[i][j] = max(vmn[i][j-1], tmp_1);
            vmx[i][j] = min(vmx[i][j-1], tmp_2);
            if (vmn[i][j] > vmx[i][j]) {
                satisfy = false;
                break;
            }
        }
        if (satisfy && dfs(j+1))
            return true;
    }
    return false;
}

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
            vmx[i][j] = p - 1;
        }
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= m; j++)
            comp[i][j] = arr[i][j] - (comp[i-1][j-1] + comp[i-1][j] + comp[i][j-1]);
    // Attempting to create first level, by searching
    // and iterate the rest with searching, no cuts
    for (int init_val = 0; init_val < p; init_val++) {
        res[1][1] = init_val;
        // Given the case that search completes, save the results
        if (dfs(2)) {
            for (int i = 2; i <= n; i++)
                res[i][1] = vmn[i][m];
            for (int i = 2; i <= n; i++)
                for (int j = 2; j <= m; j++)
                    res[i][j] = comp[i][j] + odd(j) * res[i][1] + odd(i) *
                        res[1][j] + even(i+j+1) * res[1][1];
            break;
        }
    }
    // Output result, and such a result is guranteed
    // And the format is really devastating
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            printf("%d%s", res[i][j], j == m ? "\n" : " ");
    return 0;
}