CF2056A Shape Perimeter

在一张无限大的纸上有一个 $m \times m$ 的正方形印章。最初，印章的左下角与纸张的左下角对齐。你会得到两个长度为 $n$ 的整数序列 $x$ 和 $y$。对于每一步 $i$（从 $1$ 到 $n$），会发生以下操作： - 将印章向右移动 $x_i$ 个单位，向上移动 $y_i$ 个单位。 - 将印章按压在纸上，在当前位置留下一个 $m \times m$ 的有色正方形。 注意，序列 $x$ 和 $y$ 的每个元素都满足特殊约束：$1 \le x_i, y_i \le m - 1$。 注意，你不会在纸张的左下角按压印章。具体可参考题目下方的说明图片。 可以证明，所有操作完成后，纸上的有色区域是一个连通的整体。请你求出这个有色区域的周长。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$2 \le m \le 100$），分别表示操作次数和正方形印章的边长。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le m - 1$），分别表示第 $i$ 次操作中印章向右和向上移动的距离。 注意，所有测试用例的 $n$ 之和没有额外限制。

对于每个测试用例，输出一个整数，表示纸上有色区域的周长。

在第一个样例中，印章边长为 $3$，共按压 $4$ 次，坐标分别为 $(1, 1)$、$(3, 3)$、$(5, 4)$ 和 $(6, 6)$。纸张上的效果如下图所示：  其中，第一次按压形成的正方形为蓝色，第二次为红色，第三次为绿色，第四次为紫色。合并后的区域如下图所示：  从图中可以看出，这个区域的周长为 $32$。 由 ChatGPT 4.1 翻译