M-网格谜题_第十一届"图灵杯"NEUQ-ACM程序设计竞赛

网格谜题

比赛主页

时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

你有一个神奇的网格图，这个网格一共有 $n$ 行 $m$ 列共 $n \times m$ 个格点，并且每个格点上都有一个权重 $w_{i,j}$ （表示第 $i$ 行第 $j$ 列的网格的权重为 $w_{i,j}$ ），另外这个网格还有一个固定的操作代价 $x$ 。

你可以对网格进行如下操作：

选择两个相邻 $^{\dagger}$ 的且不属于同一个连通块的格点，并且要求两个格点各自所属的连通块的权重和不小于 $x$ ，则将这两个连通块进行合并，并且合并后的连通块权重为合并前的两个连通块的权重和减去 $x$ 。也就是说，如果选择了 $u$ 和 $v$ 两个连通块进行合并 $(w_u + w_v \geq x)$ ，合并后的新连通块的权重为 $w_u + w_v - x$ 。

初始时，网格中的每一个格点是一个单独的连通块，你的目标判断这个网格是否可以通过若干次上述操作，将该网格的所有格点合并成一个连通块，如果可以，请给出任意一种可行的操作方案。

${\dagger}$ 相邻是指两个格点的坐标距离为1，例如第2行第2列的格点和第2行第3列的格点相邻，但是第2行第2列的格点和第3行第3列的格点不相邻

输入描述:

第一行包含三个整数 $n$ , $m$ , $x$ $(1 \leq n \leq 10^6 , 1 \leq m \leq 10^6,n \cdot m \leq 10^6 , 1 \leq x \leq 10^9)$ ，分别表示网格的行数、列数和操作的代价。

接下来 $n$ 行，每行包含 $m$ 个整数 $w_{i,j} (0 \leq w_{i,j} \leq 10^9)$ ，表示整个网格中，每一个格点的权重。

输出描述:

如果问题可行，第一行输出一行字符串“YES”。

第二行输出一个整数 $N$ 表示操作次数。

接下来 $N$ 行每行输出四个整数 $x_u$ , $y_u$ , $x_v$ , $y_v$ 分别表示所合并的两个格点的坐标。

如果问题不可行，只输出一行字符串“NO”。

示例1

输入

复制

2 2 3
1 2
3 4

输出

复制

说明

对于样例1：

初始时的网格：

进行第一次合并后的网格：

进行第二次合并后的网格：

进行第三次合并后的网格：

示例2

输入

复制

2 2 4
1 2
3 4

输出

复制

NO