#1486. 「2020 集训队论文」网格图哈密顿路

「2020 集训队论文」网格图哈密顿路

题目描述

你有一个 nnmm 列的网格图。定义 (x,y)(x, y) 表示网格图中第 xx 行第 yy 列的格子,则网格图左上角的格子可被表示为 (1,1)(1, 1),右下角的格子可被表示为 (n,m)(n, m)

现在这个网格图被挖掉了一个格子 (wx,wy)(wx, wy),你需要判断是否存在一条从 (sx,sy)(sx, sy) 出发的哈密顿路径,如果有则还需要输出任意一组合法方案(即不需经过也不能经过 (wx,wy)(wx, wy) 的且起点为 (sx,sy)(sx, sy) 的哈密顿路径)。

输入格式

有多组数据。第一行一个正整数 TT,表示数据组数。

接下来 TT 行,每行六个正整数 n,m,wx,wy,sx,syn,m,wx,wy,sx,sy,含义如题目描述中所示。其中 $1\le wx,sx\le n, 1\le wy, sy\le m, (wx,wy)\neq (sx,sy)$。

输出格式

对于每组数据:

若无解则仅输出一行一个整数 1-1,否则:

先输出一行一个正整数 lenlen,表示哈密顿路径长度,显然 len=nm1len = nm - 1

接下来 lenlen 行,每行两个正整数 (x,y)(x, y),表示每一步所走到的格子的坐标,显然第一行应输出 (sx,sy)(sx, sy)

样例

3
2 5 2 3 1 1
4 4 2 2 1 1
5 5 1 1 5 1
9
1 1
2 1
2 2
1 2
1 3
1 4
2 4
2 5
1 5
-1
24
5 1
4 1
3 1
2 1
2 2
1 2
1 3
1 4
1 5
2 5
3 5
4 5
5 5
5 4
5 3
5 2
4 2
3 2
3 3
2 3
2 4
3 4
4 4
4 3

第一组数据的方案如下:

page3image1264.png

对于第二组数据,可以证明不存在合法方案。

第三组数据的方案如下:

page4image1424.png

数据范围与提示

对于所有数据,保证 1n,m2001\le n, m\le 200(n+m)2000\sum (n + m)\le 2000

子任务编号 n,mn,m\le 特殊性质 子任务分值
11 44 66
22 200200 n4n\le4 2020
33 n,mn,m 均为奇数 1313
44 sx=sy=1sx=sy=1 1010
55 wx=wy=1wx=wy=1 1515
66 3636