P10874 [COTS 2022] 旅程 Dugput（非官方数据）

译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T1。$\texttt{5s,0.5G}$。 - **输入格式有微调。** - **官方数据有误。** 部分 out 文件是使用树姐姐 [ hhoppitree](https://www.luogu.com.cn/user/183609) 的代码生成的。如果出现了分数 $\gt 100$ 的情况，欢迎联系搬题人更新数据。

构造一个 $N\times M$ 的网格图，边权均为 $1$，每条边可以存在或者不存在。 在连通的前提下，最大化 $(A,B)$ 到 $(C,D)$ 的最短路长度。 **此处路径长度定义为路径经过的节点个数。**

**本题单个测试点内含有多组测试数据。** 第一行，两个整数 $\mathrm{type},T$，表示测试数据类型和测试数据组数。 接下来 $T$ 行，每行 $6$ 个整数 $N,M,A,B,C,D$，含义见题面。

每组测试数据输出若干行。 - $\mathrm{type}=0$：「构造」类数据 此类数据中，你需要构造一个网格图。输出 $(2N-1)$ 行，每行 $(3M-2)$ 个字符。 其中，第 $(2i-1)$ 行的第 $(3j-2)$ 个字符代表点 $(i,j)$。当 $(i,j)=(A,B)$ 或 $(S,T)$ 时，用 `*`（ASCII 42）表示；否则用 `o`（ASCII 111）表示。 对于同一行的两个点 $(i,j),(i,j+1)$，若有边，则用 `--`（ASCII 45）填充它们之间的两个空格；否则不填充。 对于同一列的两个点 $(i,j),(i+1,j)$，若有边，则用 `|`（ASCII 124）填充它们之间的一个空格；否则不填充。 未填充的区域均用空格补齐。不要输出多余的空格和空行。 可参阅样例输出。 - $\mathrm{type}=1$：「传统」类数据 只需要输出一行一个整数，表示最短的最长路长度。

对于 $100\%$ 的数据，保证： - $1\le N,M\le 5\, 000$； - $1\le T\le 1\, 600$； - $1\le A,C\le N$，$1\le B,D\le M$； - $(A,B)\neq (C,D)$。 | 子任务编号 | $N\cdot M\in $ | $M\le $ | $\mathrm{type}=$ | 分值 | |:-----:|:------:| :----: | :--: | :--: | | $1$ | $[2,100]$ | $5\, 000$ | $0$ | $20$ | | $2$ | $[2,1\, 000]$ | $5\, 000$ | $0$ | $25$ | | $3$ | $[2,15\, 000]$ | $3$ | $0$ | $15$ | | $4$ | $[2,100\, 000]$ | $5\, 000$ | $0$ | $25$ | | $5$ | $[2,100\, 000]$ | $5\, 000$ | $1$ | $15$ | 【评分方式】 - $\mathrm{type}=0$：「构造」类数据 记 $d_i$ 为第 $i$ 组测试数据中，你构造的方案中的最短路长度，$D_i$ 为可能的最长最短路长度。记 $$K=\frac{1}{Q}\sum_{i=1}^Q\frac{d_i}{D_i}$$ 当 $K=1$ 时，该测试点得满分；否则得 $0.7\cdot K$ 倍测试点得分的分数。 每个子任务的得分为所有测试点得分的 $\min$。 例如，样例 $1$ 的输出得满分；对于样例 $2$，$\displaystyle k=\frac{1}{2}\left(\frac{3}{5}+\frac{5}{9}\right)=\frac{31}{45}$，将得到 $\displaystyle 0.7\cdot \frac{31}{45}\approx 0.482$ 倍测试点得分的分数。 - $\mathrm{type}=1$：「传统」类数据 和传统题评分方式相同。