1. 题意理解

我们有一个 $n \times m$ 的矩阵，初始全 $0$。

• 每行有一个按钮，向左转一次，该行所有元素 +1；向右转一次，该行所有元素 -1。
• 每列有一个按钮，向左转一次，该列所有元素 +1；向右转一次，该列所有元素 -1。
• 给定 $k$ 个位置 $(x_i, y_i)$ 和目标值 $c_i$，要求最终这些位置的值恰好等于 $c_i$。
• 问是否存在一种操作方案（每行、每列可以任意左转或右转若干次，可以是负数次，即反向转），使得所有绿宝石位置满足条件。

2. 建立数学模型

设：

• 第 $i$ 行的净操作次数为 $r_i$（左转为正，右转为负，即该行整体加 $r_i$）。
• 第 $j$ 列的净操作次数为 $s_j$（左转为正，右转为负，即该列整体加 $s_j$）。

那么矩阵中位置 $(i, j)$ 的最终值为： [ a_{i,j} = r_i + s_j ] 因为初始是 $0$，行操作加 $r_i$，列操作加 $s_j$。

3. 约束条件

对于每个绿宝石 $(x, y, c)$，要求： [ r_x + s_y = c ] 其中 $c$ 已知。

所以问题转化为：

给定 $k$ 个形如 $r_x + s_y = c$ 的方程，问是否存在整数解 $(r_1, \dots, r_n, s_1, \dots, s_m)$。

4. 方程组的可解性分析

这是一个线性方程组，变量是 $r_i$ 和 $s_j$，方程数 $k$，变量数 $n+m$。

但方程形式特殊：每个方程只涉及一个 $r$ 和一个 $s$。

我们可以把它看作一个二部图：

• 左部 $n$ 个节点表示 $r_1, \dots, r_n$。
• 右部 $m$ 个节点表示 $s_1, \dots, s_m$。
• 每个条件 $r_x + s_y = c$ 是连接左部 $x$ 与右部 $y$ 的一条边，权值为 $c$。

5. 判断有解的方法

对于二部图的每个连通分量，我们可以任意设定其中一个变量的值，然后沿着边推出其他所有变量的值。

推导过程：
设连通分量中某点 $r_p = t$（$t$ 任意整数），则对于边 $(p, q)$ 有 $s_q = c - t$；对于边 $(q, p')$ 有 $r_{p'} = c' - s_q = c' - (c - t) = (c' - c) + t$，等等。
最终整个连通分量的变量都表示为 $t + \text{常数}$ 的形式。

6. 出现矛盾的情况

在推导过程中，如果某条边 $(u, v)$ 的权值 $c$ 与已算出的 $r_u$ 和 $s_v$ 不满足 $r_u + s_v = c$，则无解。

具体来说，设连通分量中我们得到： [ r_i = t + \alpha_i, \quad s_j = -!t + \beta_j ] 那么对于边 $(i, j)$ 应有： [ (t + \alpha_i) + (-!t + \beta_j) = \alpha_i + \beta_j = c_{ij} ] 这个 $\alpha_i + \beta_j = c_{ij}$ 必须成立，与 $t$ 无关。
所以只要在设定 $t=0$ 时检查所有边是否满足即可。

7. 算法步骤（思路）

1. 构建二部图，节点为行变量 $r_i$ 和列变量 $s_j$。
2. 用 BFS/DFS 找出每个连通分量。
3. 对每个连通分量：
   • 任选一个节点（如某个 $r_a$），设 $r_a = 0$。
   • 推导出该分量中所有 $r_i$ 和 $s_j$ 的值（相对于 $t=0$）。
   • 检查该分量中所有边 $(i, j)$ 是否满足 $r_i + s_j = c$。
   • 若不满足，返回 No。
4. 所有分量都满足则输出 Yes。

8. 样例验证

样例 1
$n=2, m=2, k=4$
条件： [ r_1 + s_1 = 0,\quad r_1 + s_2 = 0,\quad r_2 + s_1 = 2,\quad r_2 + s_2 = 2 ] 从 $r_1=0$ 得 $s_1=0, s_2=0$；
从 $r_2 + s_1 = 2$ 得 $r_2=2$；
检查 $r_2 + s_2 = 2+0=2$ 满足。
所以 Yes。

样例 2
条件： [ r_1 + s_1 = 0,\quad r_1 + s_2 = 0,\quad r_2 + s_1 = 2,\quad r_2 + s_2 = 1 ] 从 $r_1=0$ 得 $s_1=0, s_2=0$；
从 $r_2 + s_1=2$ 得 $r_2=2$；
检查 $r_2 + s_2 = 2+0=2 \neq 1$，矛盾。
所以 No。

9. 结论

这个问题本质是判断一个特殊的二部图线性系统是否有解，可以通过对每个连通分量赋值并检查一致性来解决，时间复杂度 $O(n+m+k)$。